yukicoder : No.715 集合と二人ゲーム

遅刻したこともありバグを直しきれず。
https://yukicoder.me/problems/no/715

問題

整数集合を用いて２人で交互にターンが来るゲームを行う。
自分の手番では集合中１つの値を指定すると、集合から差の絶対値が１以下の要素がすべて消える。

自分の手番で全要素が消えると勝ちとなる場合、最適手を取ると勝者はどちらか。

解法

元の整数集合について、重複を除いたのち連続する整数群ごとにグループわけしよう。
各グループについて、そこに属する整数の数をnとしたとき、nに対応するgrundy数grundy(n)をそれぞれ求めてxorを取り、0かどうか判定すればよい。

grundy(n)は愚直に求めると、先手がとる位置をn通り試すとして、メモ化再帰してもO(n^2)かかる。
しかし小さい値で試すと5以下の値しかとらないので、先手がとる位置は100通り程度試せば十分である。
実際grundy(n)は周期34となるらしい。

int N;
set<int> S;

int gr[505050];

int hoge(int v) {
	if(gr[v]>=0) return gr[v];
	
	int mask=0;
	for(int i=1;i<=min(50,v);i++) {
		int L=max(0,i-2);
		int R=max(0,v-(i+1));
		mask |= 1<<(hoge(L)^hoge(R));
	}
	gr[v]=0;
	while(mask & (1<<gr[v])) gr[v]++;
	return gr[v];
	
}


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	MINUS(gr);
	cin>>N;
	FOR(i,N) cin>>x, S.insert(x);
	
	int pre=*S.begin(),first=*S.begin();
	int nim=0;
	FORR(s,S) {
		if(s>pre+1) {
			nim ^= hoge(pre-first+1);
			first=s;
		}
		pre=s;
	}
	nim ^= hoge(pre-first+1);
	
	if(nim==0) cout<<"Second"<<endl;
	else cout<<"First"<<endl;
	
	
}

まとめ

CFが始まりそう～。