87 C Interesting Game
問題
二人が交互に次の操作を行うようなゲームがある。
- はじめはN個の石の山が一つある。
- 手番のプレイヤーは、一つの山を選び、それをk個の山に分裂させる。
- k個の山はa1-a2=a2-a3=...=ak-1-ak=1を満たす必要がある。
- 山を分裂させられなくなったプレイヤーの負け。
お互いに最善を尽くした場合どちらが勝つかを求め、
先手が勝つなら、先手の最初の手番でいくつの山に分裂させるか、最小の山の数を出力し、
後手が勝つなら-1を出力せよ。
制約条件
N≦10^5
方針
Grundy Numberを計算する。
Grundy Numberについては蟻本を参照。
山の分け方は、山を1000個未満と勝手に仮定して、
山の数をk個と置いたときに最小の山の数で二分探索するような適当な方法で実装した。
山の数を100個未満でやったらWAが出た(酷い)
ソースコード
int N,dp[100001],ans; int grundy(int n){ if(n<=2)return 0; if(dp[n]>=0)return dp[n]; set<int> s; for(int k=2;k<1000;k++){ int lo=-n,hi=n,mid; while(lo+1<hi){ mid=(lo+hi)/2; int sum=k*mid+k*(k-1)/2; if(sum>n)hi=mid; else lo=mid; } int sum=k*lo+k*(k-1)/2; if(lo>0&&sum==n){ int g=0; rep(i,k)g^=grundy(lo+i); if(n==N&&g==0)ans=min(ans,k); s.insert(g); } } for(int i=0;;i++)if(!s.count(i))return dp[n]=i; } void run() { memset(dp,-1,sizeof(dp)); cin>>N; ans=inf; if(!grundy(N))cout<<-1<<endl; else cout<<ans<<endl; }