かなり悩んだけどわかると一瞬。
https://www.hackerrank.com/contests/world-codesprint-13/challenges/balanced-sequence
問題
"()"で構成される偶数長の文字列が与えられる。
以下の処理を繰り返して、文字列を括弧の整合性が取れた状態にしたい。
- 文字列の部分文字列を選択し、その範囲を前後反転したのち、"("と")"を入れ替える
最小何回処理を行えばよいか。
解法
元々"()"と開き括弧と閉じ括弧の対応が取れている部分は、全体を含むような部分文字列を選択しても、やはりその対応は維持される。
よって、そのような対応が取れている括弧対を取り除こう。
これはStackを使って容易に解決できる。
すると残る形状は、閉じ括弧がいくつかあった後、開き括弧がいくつかある状態になる。
開き括弧が1個以上、閉じ括弧が1個以上あればそれぞれ1回処理が必要になるので、解は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; }
まとめ
考察は重いけど、実装は非常に軽い。