Codeforces #184 Div2. E. Playing with String

回答者数はDと同じぐらいの問題。
http://codeforces.com/contest/305/problem/E

問題

文字列に対し、２人で交互に順番で以下の処理を行うゲームを行う。

• 複数の文字列から１つ選択する（初期状態は文字列は１つ）
• 選んだ文字列の中で、両端以外で両隣の文字が等しい文字がある場合、そこで文字列を分割して３つに分ける
• 上記分割ができないなら、その人は負け

初期の文字列に対し、先手と後手どちらが勝てるか答えよ。
また、先手有利なら初手で分割する文字を返せ。

解法

典型的なnimである。
（分割可能）＝（両隣が同じ文字）である文字が何個連続しているか、についてgrundy数を作る。

先手有利の場合、nimを0にするような分割位置を求めればよい。

int L;
char S[5003];
vector<pair<int,int> > G;
int gr[5002],mex[5002];

void solve() {
	int f,r,i,j,k,l, x,y,ma,nt;
	
	gr[1]=gr[2]=1;
	for(i=3;i<=5000;i++) {
		ZERO(mex);
		mex[gr[i-2]]++;
		mex[gr[i-3]]++;
		for(j=2;j<=i-2;j++) mex[gr[j-1]^gr[i-(j+2)]]++;
		for(j=0;mex[j];j++);
		gr[i]=j;
	}
	
	
	GETs(S);
	L=strlen(S);
	
	j=0;
	for(i=1;i<L;i++) { // i=L-1 must fail 
		if(S[i-1]==S[i+1]) j++;
		else {
			if(j) G.push_back(make_pair(i-j,j));
			j=0;
		}
	}
	
	int nim=0;
	ITR(it,G) nim ^= gr[it->second];
	
	if(nim==0) {
		_P("Second\n");
	}
	else {
		_P("First\n");
		ITR(it,G) {
			FOR(j,it->second) {
				if((gr[max(0,j-1)]^gr[max(0,it->second-(j+2))])==(nim^gr[it->second])) {
					_P("%d\n",it->first+j+1);
					return;
				}
			}
		}
	}
	
	return;
}

問題

nim、Grundy数の良い練習になるね。