某岛

… : "…アッカリ~ン . .. . " .. .
December 15, 2015

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?…

先证明前者。。
令 $$q = 1-p, r = \frac{q}{p}, f_x $$ 表示当前有 $$x$$ 时的期望,假设每次只压 1,我们有:
f[m] = pf[m+1] + qf[m-1]
f[0] = 1
f[1] = 0

解得:$$, f_m = \frac{1-r^m}{1-r^n}$$。(随机徘徊。。。

考虑反证法,如果不一定是每次只压 1,那么上面只能是不等式,首先有 $$f_m \geq \frac{1-r^m}{1-r^n}$$
再者如果存在 1 以外的最优方案,假设为 d,那么有
$$f_m = pf_{m+d} + qf_{m-d} \geq p\frac{1-r^{m+d}}{1-r^n} + q\frac{1-r^{m-d}}{1-r^n} $$

。。。我们要证明这个值 < $\frac{1-r^m}{1-r^n}$。

化简一下得:$$ 1-pr^{m+d}-qr^{m-d} < 1-r^m$$?
。。。但是我好像推不过去。。。

换个方法。。。

把 d 的情况看作是若干 1 的情况叠加成的(+-d 时停止)。。
那么为了得到 +d,我们要么一步走过去 p。
要么通过若干 1 的情况叠加过去。。。($$\frac{1-r^d}{1-r^{2d}}$$)
通过一些微积分的知识。。。(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");
    }
}