Codeforces #282 Div1 A. Treasure

久々のCodeforces Div1回。
AB解いたもののAで未初期化変数アクセスバグで無駄に時間をロスしてレート微減。
http://codeforces.com/contest/494/problem/A

問題

'('、')'、'#'の３種の文字で構成された文字列がある。
#は1文字以上の閉じ括弧と置換することができる。

置換後の文字列が開き括弧と閉じ括弧の対応が取れた状態になるような置換方法があれば、その対応方法を答えよ。

解法

条件を満たすには、文字列を先頭から見ていって常に開き括弧の数が閉じ括弧の数以上でなければならない。
よって、できるだけ'#'は最小限の閉じ括弧1個に置換していく。
途中、閉じ括弧の方が多くなってしまったら条件を満たす置換はない。

最終的に開き括弧と閉じ括弧の数が一致するようにするため、閉じ括弧１個ずつの置換では開き括弧と閉じ括弧の数に一致しない場合、最後の'#'に差分を任せればよい。

ただ、最後の'#'に差分を埋めるだけの閉じ括弧を割り当てることで、途中閉じ括弧の方が大きくなってしまわないよう再度検証する必要がある。

string S;
int V;
int ma;

void solve() {
	int i,j,k,l,r,x,y; string s;
	cin>>S;
	
	ma=0;y=0;
	FOR(i,S.size()) {
		if(S[i]=='(') V++;
		if(S[i]=='#') V--,y++,ma=V;
		if(S[i]==')') V--;
		ma=min(ma,V);
		
		if(V<0) return _P("-1\n");
	}
	
	if(V==0) {
		FOR(i,y) _P("1\n");
	}
	else {
		if(ma>=V) {
			FOR(i,y-1) _P("1\n");
			_P("%d\n",V+1);
		}
		else {
			_P("-1\n");
		}
	}
}

まとめ

実装は単純だけどちょっと考える問題。