Codeforces #794 : Div1 B. Linguistics

不参加だった回。
https://codeforces.com/contest/1685/problem/B

問題

文字列Sが与えられる。
'A'をa個、'B'をb個、'AB'をc個、'BA'をd個任意の順で連結できるとき、Sを構成できるか判定せよ。

解法

AとBの総数が一致しない場合は明らかに構成不可。
S中で同じ文字が2連続した場合、そこの境目は必ず'A''B''AB''BA'の境界が来る。
よって、そのような箇所でSを分割しよう。

Sを分割した文字列は、ABABAB...かBABABA...となる。
分割した文字列長Lが奇数の時、'AB'と'BA'は合計floor(L/2)取れ、'AB'と'BA'の配分は任意である。
Lが偶数の場合、ABABAB...からは'AB'はL/2個取れるが、'BA'は(L/2-1)個しか取れない。
よってそれぞれ、極力多く取れるほうを取っていけばよい。

int T,A,B,C,D;
string S;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>A>>B>>C>>D>>S;
		int NA=0;
		int NB=0;
		vector<string> V;
		string cur;
		FORR(c,S) {
			if(c=='A') NA++;
			if(c=='B') NB++;
			if(cur.size()&&cur.back()==c) {
				V.push_back(cur);
				cur="";
			}
			cur+=c;
		}
		V.push_back(cur);
		if(NA!=A+C+D||NB!=B+C+D) {
			cout<<"NO"<<endl;
			continue;
		}
		vector<int> X[3];
		FORR(c,V) {
			if(c.size()%2) X[0].push_back(c.size()/2);
			else X[c[0]-'A'+1].push_back(c.size()/2);
		}
		sort(ALL(X[1]));
		FORR(a,X[1]) {
			x=min(a,C);
			a-=x;
			C-=x;
			x=max(0,min(a-1,D));
			D-=x;
		}
		sort(ALL(X[2]));
		FORR(a,X[2]) {
			x=min(a,D);
			a-=x;
			D-=x;
			x=max(0,min(a-1,C));
			C-=x;
		}
		C+=D;
		FORR(v,X[0]) C-=v;
		if(C<=0) cout<<"YES"<<endl;
		else cout<<"NO"<<endl;
	}
}

まとめ

ちょっと戸惑うけど1000ptにはちょうどいい問題か。