hdu 2516-石ころ取りゲーム（フィボナッチのゲーム）【ゲームの二分検索】
6813 ワード
http://acm.hdu.edu.cn/showproblem.php?pid=2516
砂利取りゲーム
Time Limit：2000/1000 MS（Java/Others） メモリLimit：32768/32768 K（Java/Others）Total Submission（s）：3248 Acceepted Submission(s)：1897
Problem Description
1山の石はn個があり、2人が順番に取ります。先取者は1回目に何個かを取りますが、全部取り終わるわけにはいきません。以後は毎回取る石の数は前回の取りの2倍を超えてはいけません。勝ち.先取者は負けて「Second win」を出力します。先取者は勝ちに「First win」を出力します。
Input
複数のグループを入力してください。グループの1行目は2<=n<2^31.n=0で終了します。
Output
先取者はマイナスに「Second win」を出力します。先取者は勝ちに「First win」を出力します。
Sample Outputを参照してください。
Sample Input
2
13
10000
0
Sample Output
Second win
Second win
First win
法則を探しましょう。分析した結果、必敗状態は2、3、5、8、13、21…であると判断されたが、必敗状態はフィボナッチ数列であることがわかった。その後、もしnがフィボナッチの数列の元素であれば、必ず失敗します。さもないと、必ず勝つ
次は数学の証明を見ます。
「Wythoffゲーム」が「Beatty定理」を必要とするように、ここでは「Zeckendorf定理」（斉肯多夫定理）を借りる必要があります。どんな正の整数もいくつかの不連続なFibonacciの数の和として表現できます。
まずFIBの数列の必敗証明を見てください。
1、i=2の場合、先手は1本しか取れません。明らかに負けます。結論は成立します。
2、i<=kと仮定すると、結論が成立する。
i=k+1の場合は、f[i]=f[k]+f[k-1]となる。
この一山の石を二つの山と見なして、k山とk-1山と略称します。
（必ず二つの山のように見えます。先の手が初めて取った石の数がf[k-1]以上であれば、後手はf[k]を直接取ってもいいです。f[k]<2*f[k-1]からです。
k-1ヒープについては、先手がどのように取っても後手は最後の一粒まで取れます。後手が最後に取った石の数xを分析します。
先手が初めて取った石の数y>=f[k-1]/3であれば、この山の残りの石の数は2 y以下、つまり後手は直接取り終わる。この時x=f[k-1]-yはx<=2/3*f[k-1]である。
2/3*f[k-1]と1/2*f[k]の大きさを比較します。つまり4*f[k-1]と3*f[k]の大きさは、数学的帰納法によっては出にくく、後者が大きいです。
だから私たちはx<1/2*f[k]をもらいます。
つまり、後ろの手でk-1山を取った後、先にk山を全部取れません。ですから、ゲームのルールは変わりません。k山に対して、後ろの手は最後の一つまで取れます。だから後手は必ず勝ちます。
つまり、i=k+1の場合、結論は依然として成立しています。
FIB数ではない場合は、まず分解します。
分解する時は、できるだけ大きなFibonacciを取ります。
例えば、85：85を55と89の間に分解し、85=55+30と書くことができ、30,30を21と34の間に分解し続けることができるので、30=21+9と書くことができます。
これによって類推して、最後に85=55+21+8+1に分解します。
nを書き上げることができます。 n=f[a 1]+f[a 2]+…+f[ap]です。（a 1>a 2>…>ap）
私たちは先にf[ap]を取ってください。つまり一番小さいこの山です。各f間が連続していないので、a(p-1)>ap + 1,f[a(p-1)>>2*f[ap]があります。つまり、後手はf[a(p-1)の山しか取れません。一回では取りきれません。
この時、後ろの手はこのサブゲーム（f[a(p-1)]という石の山しかなく、後の手が先に取る）の必敗状態に相当します。つまり、先にこの山の最後の石を手に取ってもいいです。
同じ理屈から分かるように、これからの一つ一つに対して、先手は全部この山の最後の石を取って、ゲームの勝利を獲得することができます。
コード:
砂利取りゲーム
Time Limit：2000/1000 MS（Java/Others） メモリLimit：32768/32768 K（Java/Others）Total Submission（s）：3248 Acceepted Submission(s)：1897
Problem Description
1山の石はn個があり、2人が順番に取ります。先取者は1回目に何個かを取りますが、全部取り終わるわけにはいきません。以後は毎回取る石の数は前回の取りの2倍を超えてはいけません。勝ち.先取者は負けて「Second win」を出力します。先取者は勝ちに「First win」を出力します。
Input
複数のグループを入力してください。グループの1行目は2<=n<2^31.n=0で終了します。
Output
先取者はマイナスに「Second win」を出力します。先取者は勝ちに「First win」を出力します。
Sample Outputを参照してください。
Sample Input
2
13
10000
0
Sample Output
Second win
Second win
First win
法則を探しましょう。分析した結果、必敗状態は2、3、5、8、13、21…であると判断されたが、必敗状態はフィボナッチ数列であることがわかった。その後、もしnがフィボナッチの数列の元素であれば、必ず失敗します。さもないと、必ず勝つ
次は数学の証明を見ます。
「Wythoffゲーム」が「Beatty定理」を必要とするように、ここでは「Zeckendorf定理」（斉肯多夫定理）を借りる必要があります。どんな正の整数もいくつかの不連続なFibonacciの数の和として表現できます。
まずFIBの数列の必敗証明を見てください。
1、i=2の場合、先手は1本しか取れません。明らかに負けます。結論は成立します。
2、i<=kと仮定すると、結論が成立する。
i=k+1の場合は、f[i]=f[k]+f[k-1]となる。
この一山の石を二つの山と見なして、k山とk-1山と略称します。
（必ず二つの山のように見えます。先の手が初めて取った石の数がf[k-1]以上であれば、後手はf[k]を直接取ってもいいです。f[k]<2*f[k-1]からです。
k-1ヒープについては、先手がどのように取っても後手は最後の一粒まで取れます。後手が最後に取った石の数xを分析します。
先手が初めて取った石の数y>=f[k-1]/3であれば、この山の残りの石の数は2 y以下、つまり後手は直接取り終わる。この時x=f[k-1]-yはx<=2/3*f[k-1]である。
2/3*f[k-1]と1/2*f[k]の大きさを比較します。つまり4*f[k-1]と3*f[k]の大きさは、数学的帰納法によっては出にくく、後者が大きいです。
だから私たちはx<1/2*f[k]をもらいます。
つまり、後ろの手でk-1山を取った後、先にk山を全部取れません。ですから、ゲームのルールは変わりません。k山に対して、後ろの手は最後の一つまで取れます。だから後手は必ず勝ちます。
つまり、i=k+1の場合、結論は依然として成立しています。
FIB数ではない場合は、まず分解します。
分解する時は、できるだけ大きなFibonacciを取ります。
例えば、85：85を55と89の間に分解し、85=55+30と書くことができ、30,30を21と34の間に分解し続けることができるので、30=21+9と書くことができます。
これによって類推して、最後に85=55+21+8+1に分解します。
nを書き上げることができます。 n=f[a 1]+f[a 2]+…+f[ap]です。（a 1>a 2>…>ap）
私たちは先にf[ap]を取ってください。つまり一番小さいこの山です。各f間が連続していないので、a(p-1)>ap + 1,f[a(p-1)>>2*f[ap]があります。つまり、後手はf[a(p-1)の山しか取れません。一回では取りきれません。
この時、後ろの手はこのサブゲーム（f[a(p-1)]という石の山しかなく、後の手が先に取る）の必敗状態に相当します。つまり、先にこの山の最後の石を手に取ってもいいです。
同じ理屈から分かるように、これからの一つ一つに対して、先手は全部この山の最後の石を取って、ゲームの勝利を獲得することができます。
コード:
1 #include <iostream>
2 #include <cstdio>
3
4 using namespace std;
5
6 int f[50],n;
7
8 bool find();
9
10 int main(){
11 f[0]=2;
12 f[1]=3;
13 for(int i=2;i<44;i++){//44
14 f[i]=f[i-1]+f[i-2];
15 }
16 while(scanf("%d",&n),n){
17 if(find()) puts("Second win");
18 else puts("First win");
19 }
20 return 0;
21 }
22 bool find(){
23 int l=0,r=43,mid;
24 while(l<=r){
25 mid=(l+r)>>1;
26 if(n==f[mid]) return true;
27 else if(n<f[mid]) r=mid-1;
28 else l=mid+1;
29 }
30 return false;
31 }