Codeforces ECR #073 : E. Game With String

だいぶパズルチックな問題。
https://codeforces.com/contest/1221/problem/E

問題

白黒で塗られた横１列のマス目がある。
ここで２人でターン制のゲームを行う。
それぞれ連続する白マスをA,Bマス選択し、黒く塗りつぶす。
選択できなくなったら負けである。

両者最適手を取るとき先手必勝か判定せよ。
なお、A＞Bである。

解法

まず白が連続する区間を長さで分類しよう。
A＞Bであることから、B以上A未満の長さの区間が1個でもあると後手が最後までそれをキープできるので後手必勝である。

以降全区間A以上の長さの場合を考える。
2B以上の長さの区間ができた状態で後手に手番を回してしまうと、上記の状態に持ち込まれるのでアウトである。
もうこの時点で、最長の区間のみA以上で、それ以外はA以上2B未満という状態になる。
最長の区間のとる位置を全部総当たりしてみよう。相手に2B以上の長さを残さないようにすると、あとは両者残された区間の偶奇で勝者が確定する。

int Q;
int A,B,N;
string S;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>Q;
	while(Q--) {
		cin>>A>>B>>S;
		S+="X";
		int cur=0;
		vector<int> V,Bs;
		FORR(c,S) {
			if(c=='X') {
				if(cur>=A) V.push_back(cur);
				else if(cur>=B) Bs.push_back(cur);
				cur=0;
			}
			else {
				cur++;
			}
		}
		if(Bs.size() || V.empty()) {
			cout<<"NO"<<endl;
			continue;
		}
		sort(ALL(V));
		reverse(ALL(V));
		if(V.size()>=2 && V[1]>=2*B) {
			cout<<"NO"<<endl;
			continue;
		}
		for(i=0;i+A<=V[0];i++) {
			j=V[0]-(i+A);
			if(i>=B*2 || j>=B*2) continue;
			if(i>=B&&i<A) continue;
			if(j>=B&&j<A) continue;
			int lef=(i>=A)+(j>=A)+V.size()-1;
			if(lef%2==0) {
				cout<<"YES"<<endl;
				break;
			}
		}
		if(i+A>V[0]) cout<<"NO"<<endl;
	}
}

まとめ

シンプルな問題設定だけど、細かいコーナーケースが多くてしんどい。