kmjp's blog

競技プログラミング参加記です

AtCoder ARC #038 : C - 茶碗と豆

この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で管理する。
すると \displaystyle \min_{0\le x \lt G_i}( F(x) ) \le i-C_iを満たす最大の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;
	
}

まとめ

部分点の解法を落ち着いて考えると満点にたどり着く良問だね。