kmjp's blog

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

AtCoder ABC #297 : G - Constrained Nim 2

確証を持たず、実験でエイヤでやってしまった…。
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