確証を持たず、実験でエイヤでやってしまった…。
https://atcoder.jp/contests/abc297/tasks/abc297_g
問題
変則的なNimを考える。
ここでは、山から取り除ける石の数が、L以上R以下に制限されている。
山の状態が与えられるとき、勝者は先手後手いずれか。
解法
実験すると石の数xの山のGrundy数はfloor*1/L)となる。
int N,L,R; int A[202020]; int gr[202020]; void solve() { int i,j,k,l,r,x,y; string s; cin>>N>>L>>R; /* for(i=1;i<=100;i++) { set<int> S; for(j=L;j<=R&&i-j>=0;j++) S.insert(gr[i-j]); while(S.count(gr[i])) gr[i]++; cout<<i<<" "<<gr[i]<<endl; } */ int nim=0; FOR(i,N) { cin>>x; x%=L+R; x/=L; nim^=x; } if(nim) { cout<<"First"<<endl; } else { cout<<"Second"<<endl; } }
まとめ
このGrundy数は覚えておいてもよさそう。
*1:x%(L+R