CPSCO2019 Session4 : E - ox Concatenation

これは本番にACできて良かったね。
https://atcoder.jp/contests/cpsco2019-s4/tasks/cpsco2019_s4_e

問題

"o","x","ox","xo"がA,B,C,D個与えられる。
これらを任意の順で連結し、文字列Sが構成できるか判定せよ。

解法

まずoxの個数を判定しよう。
次に、"ox","xo"を使い切れるか判定する。

Sを、"oxoxo..."と交互にoxが並ぶ複数の文字列に分解しよう。
この時、この長さが奇数なら、"ox"と"xo"の取れる数の合計は一定だが、偶数だとどちらかはもう片方より1個多く取れることになる。
そこで、長さが短い方から順に、「取り方によって1つ多く取れる場合は、そちらを先に取ることを試す」という貪欲順で"ox""xo"を割り当てることで最適化できる。

int N,A,B,C,D;
string S;
int M[2];
vector<pair<int,string>> V;
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>S>>A>>B>>C>>D;
	FORR(c,S) {
		if(c=='o') M[0]++;
		else M[1]++;
		if(V.empty()||V.back().second.back()==c) V.push_back({0,""});
		V.back().second.push_back(c);
		V.back().first++;
	}
	
	if(A+B+C!=M[0]) return _P("No\n");
	if(A+B+D!=M[1]) return _P("No\n");
	
	sort(ALL(V));
	FORR(v,V) {
		if(v.first%2==0) {
			x=v.first/2;
			if(v.second[0]=='o') {
				y=min(A,x);
				A-=y;
				v.first-=2*y;
			}
			else {
				y=min(B,x);
				B-=y;
				v.first-=2*y;
			}
			if(v.first) v.first--;
		}
	}
	int num=0;
	FORR(v,V) num+=v.first/2;
	if(num>=A+B) cout<<"Yes"<<endl;
	else cout<<"No"<<endl;
	
	
	
}

まとめ

ちょっと迷うのでまぁ600ptぐらいかなという問題。