AtCoder ARC #151 : C - 01 Game

まぁまぁ出来の良かった回。
https://atcoder.jp/contests/arc151/tasks/arc151_c

問題

N個のマスがあり、うち一部には0または1が書かれている。
ここで以下の2人ターン制ゲームを行う。
各自の手番では、空きマスを1つ選び0または1を書く。
その際、隣接マスがともに同じ数字になる書き方はできない。

両者最適手を取るとき、勝者はどちらか。

解法

連続する一連の空きマスについて、Grundy数を求めよう。
空きマスの両隣の数字と、空きマスの数の偶奇でGrundy数が定まる。

ll N,M;
ll X[202020],Y[202020];
ll S[100],D[100],O[100],Z[100];


void taka() {
	cout<<"Takahashi"<<endl;
	exit(0);
}
void aoki() {
	cout<<"Aoki"<<endl;
	exit(0);
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	FOR(i,M) {
		cin>>X[i]>>Y[i];
		Y[i]^=X[i]%2;
	}
	
	S[0]=0;
	D[0]=0;
	D[1]=0;
	for(i=1;i<=20;i++) {
		set<int> V;
		for(j=1;j<=i;j++) {
			V.insert(S[j-1]^S[i-j]);
			if(j>1&&j<i) V.insert(D[j-1]^D[i-j]);
		}
		while(V.count(S[i])) S[i]++;
		V.clear();
		for(j=1;j<=i;j++) {
			if(j<i) V.insert(S[j-1]^D[i-j]);
			if(j>1) V.insert(D[j-1]^S[i-j]);
		}
		while(V.count(D[i])) D[i]++;
		V.clear();
		for(j=1;j<=i;j++) {
			V.insert(S[j-1]^O[i-j]);
			if(j>1) V.insert(D[j-1]^O[i-j]);
		}
		while(V.count(O[i])) O[i]++;
		V.clear();
		for(j=1;j<=i;j++) {
			V.insert(O[j-1]^O[i-j]);
		}
		while(V.count(Z[i])) Z[i]++;
		
		cerr<<i<<" "<<S[i]<<" "<<D[i]<<" "<<O[i]<<" "<<Z[i]<<endl;
	}
	
	if(M==0) {
		if(N%2==1) taka();
		if(N%2==0) aoki();
	}
	
	ll nim=0;
	nim^=X[0]-1;
	nim^=N-X[M-1];
	FOR(i,M-1) {
		ll s=X[i+1]-X[i]-1;
		s%=2;
		if(Y[i]==Y[i+1]) {
			nim^=s;
		}
		else {
			nim^=s^1;
		}
	}
	if(nim) taka();
	else aoki();
	
	
}

まとめ

おそらく本番実験でこの特徴を求めている。
これ本番中に実験でなく考察でGrundy数求めた人どれぐらいいるんだろ。