World CodeSprint 13 : D. Balanced Sequence

かなり悩んだけどわかると一瞬。
https://www.hackerrank.com/contests/world-codesprint-13/challenges/balanced-sequence

問題

"()"で構成される偶数長の文字列が与えられる。
以下の処理を繰り返して、文字列を括弧の整合性が取れた状態にしたい。

• 文字列の部分文字列を選択し、その範囲を前後反転したのち、"("と")"を入れ替える

最小何回処理を行えばよいか。

解法

元々"()"と開き括弧と閉じ括弧の対応が取れている部分は、全体を含むような部分文字列を選択しても、やはりその対応は維持される。
よって、そのような対応が取れている括弧対を取り除こう。
これはStackを使って容易に解決できる。

すると残る形状は、閉じ括弧がいくつかあった後、開き括弧がいくつかある状態になる。
開き括弧が１個以上、閉じ括弧が１個以上あればそれぞれ１回処理が必要になるので、解は0～2の範囲に収まる。

int N;
string S;
int A,B;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>S;
	FORR(c,S) {
		if(c=='(') {
			B++;
		}
		else {
			if(B) B--;
			else A++;
		}
	}
	cout<<(A!=0)+(B!=0)<<endl;
}

まとめ

考察は重いけど、実装は非常に軽い。