無駄なコードを書いてタイムロスしてしまった。
http://yukicoder.me/problems/383
問題
初期状態でN個の石がある山が1個ある。
2人で交互に石を分割するゲームを行う。
2人は各ターンで1個山を選び、石の数を均等に2つまたは3つに分ける。
1個になった山はそれ以上分割できない。
分割できる山がなくなった場合負けとなる。
互いに最適手を取った場合、勝者はどちらか。
解法
石の数に対するGrundy数を数えよう。
Grundy数は過去にyukicoderで登場済みだね。
yukicoder : No.103 素因数ゲーム リターンズ - kmjp's blog
int N; int grundy[101]; void solve() { int i,j,k,l,r,x,y; string s; cin>>N; grundy[1]=0; for(i=2;i<=100;i++) { set<int> s; s.insert(grundy[i/2]^grundy[(i+1)/2]); if(i>=3) s.insert(grundy[i/3]^grundy[(i+1)/3]^grundy[(i+2)/3]); while(s.count(grundy[i])) grundy[i]++; } if(grundy[N]!=0) cout<<"A"<<endl; else cout<<"B"<<endl; }
まとめ
何を考えたか、最初愚直探索解を書いてしまった。
「Grundy数の問題は出たことあるので、こんなにオーソドックスなGrundy数の問題が出るわけない」という先入観にしてやられた。