こちらはすんなり。
http://yukicoder.me/problems/1016
問題
2人で交互に竹を分割するゲームを行う。
各人の手番では、手持ちの竹のうち一つを選び、以下の条件を満たす範囲で長さを3分割する。
- 各長さは正整数。
- 3つの長さは門松列を成すように並べられる。
- 3つの長さの最大値と最小値の差はD以内。
自分の手番で分割できなくなったら負けである。
初期状態で長さLの竹が1本ある場合、互いに最適手を取ったときの勝者はどちらか。
解法
Nimで解くだけ。
門松列は余り意識する必要はない。3つ異なる長さの竹に分割すれば、最長の竹を真ん中に持ってくるだけで門松列になる。
int L,D; int gr[501]; void solve() { int i,j,k,l,r,x,y; string s; cin>>L>>D; for(i=1;i<=L;i++) { set<int> me; for(x=1;x<=i-1;x++) { for(y=x+1;i-(x+y)>y;y++) { r=i-x-y; if(r-x<=D) me.insert(gr[x]^gr[y]^gr[r]); } } while(me.count(gr[i])) gr[i]++; } if(gr[L]==0) _P("matsu\n"); else _P("kado\n"); }
まとめ
竹の分割アニメーションこってるな。