Codeforces #459 Div1 A. The Monster

面倒でもCに挑めばよかったか。
http://codeforces.com/contest/917/problem/A

問題

"("")""?"で構成された文字列Sがある。
Sの連続した部分文字列のうち、"?"を適切に置き換えることで正しい括弧列にできるものはいくつか。

解法

部分文字列の開始位置を総当たりし、終了位置を徐々に伸ばしながら判定しよう。
その際、定番テクとして開き括弧と閉じ括弧の差を見ていくわけだが、"?"の場合は開き括弧を最大化する場合と、最小化する場合を考えていこう。
ただしその結果閉じ括弧の方が多くなってしまいそうなら、1つ巻き戻す。
すなわち差が-1になった時点で、閉じ括弧を開き括弧に1つ変化させ、+1にする。
ただし、開き括弧を最大化する場合より多くすることはできない。

部分文字列数が偶数になった時点で、最小値の方が0になるなら、そのタイミングで正しい括弧列を生成できるので答えに1加算する。

string S;
int N;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>S;
	N=S.size();
	
	int ret=0;
	FOR(x,N) {
		int L=0,R=0;
		for(y=x;y<N;y++) {
			if(S[y]=='(') L++,R++;
			if(S[y]==')') {
				L--,R--;
				if(L<0) L=1;
				if(L>R) break;
			}
			if(S[y]=='?') {
				L--,R++;
				if(L<0) L=1;
			}
			if(L%2==0 && L==0) ret++;
		}
	}
	cout<<ret<<endl;
	
}

まとめ

すんなり思いつけたけど、結構苦戦した人もいたようだ。