JAG Spring Contest 2015

提交地址

Overview:

做 ASC 42 的 B 題的時候遇到的問題。。。ASC 42 的題目是:
初始有 m 元錢,目標是恰好擁有 n 元錢
每輪你可以壓至多當前你所擁有的錢數進行賭博,p 的概率翻倍,q 的概率失去賭注。
至多進行 t 個回合,問最優策略下達到目標的概率。
(t <= 300, p < 50。)

YY 了一下結論,假設當前有 m 元錢,每次壓 min(m, n-m) 就可以了。
加之題目限制很強,模擬 DP 一下就出來了。在 camp 群里遂問了一下 p >= 50 的情況下結論還成立嗎。。
果然有完整版的題目。


Problem C. Casino
初始有 m 元錢,目標是擁有 >= n 元錢,
每輪你可以壓至多當前你所擁有的錢數進行賭博(必須整數),p 的概率翻倍,(1-p) 的概率失去賭注。
問最優策略下達到目標的概率,以及所有合法的第一步的方案(超過 200 個只需輸出最大和最小的 100 個)。
(0 <= p <= 1, 0 < m < n <= 10^9)

首先特判掉 p = 1 或 p = 0 的邊界情況。(由於結局固定,所以 [1, m] 都是合法解,即使加上去會超過 n。)
考慮和 ASC 那題的主要不同,主要是數據範圍變大,並且沒有了壓住次數的限制。
那麼首先考慮 p = 0.5 的情況,每輪賭注的期望收益都為 0,(與壓多少無關)。
根據鞅論中的可選停止定理。停時的鞅的期望值等於其初始值,因而在 n 終止的概率為 m/n。
(所有 [1, min(m, n-m)] 的值都為合法解)

另外兩種情況,直觀的看上去。。。

  • p > 0.5 時,平均起來,賭徒贏了錢,則隨著時間的流逝,賭徒的財產是一個下鞅。
    因而我們希望採取一種 「步步為營」 的策略,滾雪球,慢慢的積累自己的優勢。
    (直感:期待値的には良いわけだから長時間やってれば勝てるっしょ!)
  • p < 0.5 時,平均起來,賭徒輸了錢,則隨著時間的流逝,賭徒的財產是一個上鞅。 因而我們希望採取一種 「寧為玉碎」 的策略,一小博大,去希冀畢其功於一役! (直感:期待値的に不利だから長引くとジリ貧,わんちゃん狙っていくしかない!)

因而前者我們每次只壓 1,後者我們每次壓 min(m, n-m)。

。。。Is that true?...

先證明前者。。
表示當前有 時的期望,假設每次只壓 1,我們有:
f[m] = pf[m+1] + qf[m-1]
f[0] = 1
f[1] = 0

解得:。(隨機徘徊。。。

考慮反證法,如果不一定是每次只壓 1,那麼上面只能是不等式,首先有
再者如果存在 1 以外的最優方案,假設為 d,那麼有

。。。我們要證明這個值 < $\frac{1-r^m}{1-r^n}$。

化簡一下得:
。。。但是我好像推不過去。。。

換個方法。。。

把 d 的情況看作是若干 1 的情況疊加成的(+-d 時停止)。。
那麼為了得到 +d,我們要麼一步走過去 p。
要麼通過若干 1 的情況疊加過去。。。()
通過一些微積分的知識。。。(http://www.wolframalpha.com/input/?i=%281-%28%281-p%29%2Fp%29%5E2%29+-+%281-%28%281-p%29%2Fp%29%5E%284%29%29+p...

可以推斷出後者在 p>1/2 的情況下是大於 p 的。。
因而此時最優方案為 1。

Problem L. Wall Making Game

https://discuss.codechef.com/questions/26237/caos3-editorial

//}/* .................................................................................................................................. */

const int N = int(20) + 9;
char Board[N][N]; int SG[N][N][N][N];
int h, w;

int sg(int x0, int y0, int x1, int y1){
    
    int &z = SG[x0][y0][x1][y1];
    
    if (z == -1){
        if (x0 >= x1 || y0 >= y1) z = 0;
        else{
            set<int> H; FOR(x, x0, x1) FOR(y, y0, y1){
                if (Board[x][y] == '.'){
                    H.insert(sg(x0, y0, x, y) ^ sg(x0, y+1, x, y1) ^
                         sg(x+1, y0, x1, y) ^ sg(x+1, y+1, x1, y1)) ;
                }
            }
    
            REP(i, H.size()+1) if (H.find(i) == H.end()){
                z = i;
                break;
            }
        }
    }
    return z;
}


int main(){
    
#ifndef ONLINE_JUDGE
    //freopen("/users/xiaodao/desktop/Exercise/in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
#endif
    
    while (cin >> h >> w){
        REP(i, h) scanf("%s", Board[i]); FLC(SG, -1);
        puts(sg(0, 0, h, w) ? "First" : "Second");
    }
}