yukicoder : No.2278 Time Bomb Game 2

これ系のゲーム問題、すっきり書けないなぁ…。
https://yukicoder.me/problems/no/2278

問題

N個のマス目が並んでおり、それぞれA,Bの文字のいずれかが書かれている。
今K番目のマスにコインがある状態で以下のゲームを行う。

AliceとBobで行うゲームである。
今コインのあるマスにAまたはBが書かれていたら、Alice, Bobが以下のいずれかを行う。

• 左隣マスにコインを動かす
• 右隣マスにコインを動かす

上記処理をT回行う場合、最後にコインがあるマスにA,Bが書かれている場合、Alice, Bobの負けである。
互いに最適手を取るとき、勝者はどちらか。

解法

以下のように場合分けする。

• 両隣のどちらかに今いるのと同じ文字のマスがある場合
  • 2マスを往復することでTターンを消費することができる。最後のターンで相手に渡すことができれば勝てる。これは左右それぞれ最寄りの相手のマスまでの距離と偶奇で判定できる。
• 両隣のどちらも今いるのと同じ文字のマスがない場合
  • 偶数なら負け。移動先で相手が逆向きにコインを移動させるため、どうやっても勝てない。
  • 奇数なら左右両方に移動するケースを試し、いずれかで勝利できるならそちらに動かす。

int N,K,T;
string S;

int win(int cur,int left) {
	int turn=S[cur]-'A';
	
	int L,R;
	for(L=cur;L>=0;L--) if(S[L]!=S[cur]) break;
	for(R=cur;R<N;R++) if(S[R]!=S[cur]) break;
	
	int ret=turn^1;
	if(L+1==R-1) {
		ret=turn^1;
		if(left%2) {
			if(cur>0&&win(cur-1,left-1)==turn) ret=turn;
			if(cur<N-1&&win(cur+1,left-1)==turn) ret=turn;
		}
	}
	else {
		if(L>=0&&left>=cur-L&&(cur-L)%2==left%2) ret=turn;
		if(R<N&&left>=R-cur&&(R-cur)%2==left%2) ret=turn;
	}
	return ret;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>K>>T>>S;
	if(win(K-1,T)==0) {
		cout<<"Alice"<<endl;
	}
	else {
		cout<<"Bob"<<endl;
	}
}

まとめ

細かいところを詰めていくのがしんどい。