Codeforces #1051 : Div2. E. Make Good

本番割とすんなり解けているな。
https://codeforces.com/contest/2143/problem/E

問題

括弧列Sがある。
同じ文字が２連続する箇所を選び、開き括弧・閉じ括弧を反転させる処理を任意に行えるとする。
Sを正しい括弧列にできるか。できるなら一例を示せ。

解法

Sにおいて同じ文字が2連続している箇所があった場合、その2文字は任意の場所に移動でき、また閉じ括弧/開き括弧を任意に選択できる。
そこで、Sのうちまず同じ文字2連続の組を取り除こう。

あとは、Sのprefixにおいて、閉じ括弧の方が多くなりそうなタイミングがあれば、そこに開き括弧2文字を挿入するようにしよう。

int T,N;
string S;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N>>S;
		int num=0;
		string V;
		FORR(c,S) {
			if(V.size()&&V.back()==c) {
				num++;
				V.pop_back();
			}
			else {
				V.push_back(c);
			}
		}
		int pos=0;
		string R;
		FORR(c,V) {
			if(c=='(') {
				pos++;
				R+=c;
			}
			else {
				if(pos) {
					R+=c;
					pos--;
				}
				else if(num) {
					num--;
					pos++;
					R+="(()";
				}
				else {
					pos=-1;
					break;
				}
			}
		}
		if(pos==-1) {
			cout<<-1<<endl;
			continue;
		}
		FOR(i,num) {
			if(pos<=1) {
				R+="((";
				pos+=2;
			}
			else {
				R+="))";
				pos-=2;
			}
		}
		if(pos==0) {
			cout<<R<<endl;
		}
		else {
			cout<<-1<<endl;
		}
	}
	
}

まとめ

Fが解けず残念。