CodeTON Round 2 : F. Colouring Game

イギリス英語？
https://codeforces.com/contest/1704/problem/F

問題

N個のマスが並んでおり、各セル赤か青のいずれかで塗られている。
ここで2人ターン制のゲームを行う。

• 先手は、隣接する2マスを選び、白く塗る。ただし、選ぶ2マスのうちいずれかは赤くないといけない。
• 後手は、隣接する2マスを選び、白く塗る。ただし、選ぶ2マスのうちいずれかは青くないといけない。

白く塗るマスを選べない側が負けとなる。
両者最適手を取るとき、勝者はどちらか。

解法

互いに赤青マスが隣接する箇所をつぶそうとするため、赤青マスの数が異なる場合勝者は自明である。

あとは、RBRBRB....と交互に並んでいる箇所があるとき、どこをつぶすかで決まる。
F(n) := RBRB...とnマス交互に続いていると木のGrundy数

とすると、F(n)は2マス取り除く箇所を総当たりすればよいためO(n)で求めることができる。
とはいえ、F(0)～F(n)まで埋めると一見O(n^2)程度かかりそうである。
なお、F(n)はある程度以降周期34となるので、そこまでF(n)の計算に手間取らなくなる。

int T,N;
string S;

int mex[5050505];

bool hoge() {
	int i,j,k,l,r,x,y; string s;
	
	if(count(ALL(S),'R')<count(ALL(S),'B')) return 0;
	if(count(ALL(S),'B')<count(ALL(S),'R')) return 1;
	
	int nim=0;
	int num=0;
	int pre=-1;
	FORR(c,S) {
		if(pre==c) {
			nim^=mex[num];
			num=0;
		}
		pre=c;
		num++;
	}
	nim^=mex[num];
	return nim;
}
	

void solve() {
	int i,j;
	
	for(i=1;i<=1000;i++) {
		set<int> S;
		for(j=0;j<=i-2;j++) S.insert(mex[j]^mex[i-2-j]);
		while(S.count(mex[i])) mex[i]++;
	}
	
	for(i=1001;i<=5050101;i++) mex[i]=mex[i-34];
	
	cin>>T;
	while(T--) {
		cin>>N>>S;
		if(hoge()) {
			cout<<"Alice"<<endl;
		}
		else {
			cout<<"Bob"<<endl;
		}
	}
}

まとめ

どこから34って数字が出てくるんだろうな。