このGrundy数のアレンジはいい勉強になりました。
http://arc038.contest.atcoder.jp/tasks/arc038_c
問題
0~(N-1)番の番号が付いたN個の皿があり、i番目の皿にはA[i]個の豆がある。
2人交互に豆を移動するゲームを行う。
各人のターンでは、i>0であるi番の皿の豆を1つ選択しi-C[i]~i-1のどこかの皿に移動できる。
自分のターンで選択できる豆がない(=すべての豆が0番の皿にある)場合負けとなる。
最適手を取った場合、勝者はどちらになるか。
解法
典型的なGrundy数問題である。
i番の皿の豆1個に相当するGrundy数をG[i]とする。
各豆の分だけG[i]のxorを取り、それが0なら後手必勝、非0なら先手必勝である。
今回豆の総和はA[i]*Nとかなり多いが、同じ値を2回xorすると0になることから、i番の皿に豆が奇数個ある場合G[i]を1回だけxor取ればよく、偶数回ならxorを取らなくてよい。
ここで、G[i]はG[i-C[i]]~G[i-1]に含まれない最小の非負整数となる。
この判定は愚直に行うと皿1個あたりO(C[i])かかるので、全体でO(N^2)かかり満点は取れない。
満点を取るためには、「G[i-C[i]]~G[i-1]に含まれない最小の非負整数」を高速に求める必要がある。
これには最小値を管理するSegTreeを用いることができる。
G[j]=xであるような最大のj(<i)をF(x)とし、このF(x)をSegTreeで管理する。
するとを満たす最大のG[i]が「G[i-C[i]]~G[i-1]に含まれない最小の非負整数」となるので、G[i]を二分探索で求めることができる。
template<class V,int NV> class SegTree_1 { public: vector<V> val; static V const def=9999999; V comp(V l,V r){ return min(l,r);}; SegTree_1(){val=vector<V>(NV*2,def);}; V getval(int x,int y,int l=0,int r=NV,int k=1) { if(r<=x || y<=l) return def; if(x<=l && r<=y) return val[k]; return comp(getval(x,y,l,(l+r)/2,k*2),getval(x,y,(l+r)/2,r,k*2+1)); } void update(int entry, V v) { entry += NV; val[entry]=v; while(entry>1) entry>>=1, val[entry]=comp(val[entry*2],val[entry*2+1]); } }; int N; ll C[101000],A[101000]; int gr[101000]; ll grgr=0; SegTree_1<int,1<<20> seg; void solve() { int i,j,k,l,r,x,y; string s; cin>>N; FOR(i,N-1) cin>>C[i+1]>>A[i+1]; FOR(i,1<<20) seg.update(i,-1); seg.update(0,0); for(i=1;i<N;i++) { x=i-C[i]; y=0; for(j=19;j>=0;j--) if(seg.getval(0,y+(1<<j))>=x) y+=1<<j; gr[i]=y; seg.update(y,i); if(A[i]%2) grgr ^= gr[i]; } if(grgr==0) cout<<"Second"<<endl; else cout<<"First"<<endl; }
まとめ
部分点の解法を落ち着いて考えると満点にたどり着く良問だね。