SRM 688 div1 easy: ParenthesesDiv1Easy
問題
TopCoder Statistics - Problem Statement
いつもの様に valid な括弧列を定義する(stack で上手くいく〜ってアレ)。
ある括弧列 s が与えられ, これを valid な括弧列にしたい。s に対して行える操作は l, r で特徴づけられ, 次のことを順番に行う。
- [l, r] 区間の文字列を反転させる(reverse する)
- [l, r] 区間の文字について '(' は ')' に, ')' は '(' にする
10 回以内の操作で s を valid にすることができたら可能な操作のうちの一つを求めよ。
解法
まず, s の長さが奇数だったら明らかに valid に出来ません。長さが偶数の場合は実は 2 回の操作で必ず valid な括弧列に出来ます。
括弧列から, '(' と ')' で対応しているのを取り除いていくと, 結局 ))))))(((( のようなものだけ残ります。これは
- まず )))))) のところだけ処理して (((((((((( にする(A)
- 最後に valid な括弧列になるように 後半の '(' を ')' にする(B)
とやれば良いです。'(' と ')' で対応しているところは反転させてもやはり対応しているので, この操作で問題ないです。
これを実現するためにはどうするかを考えます。
[0, l] で反転させることによって 「'(' の数が ')' の数より少ない」ということがない状態にします。この条件を満たす最大の l が(A) の操作になります。
で, 次は [r, N-1] を反転させて valid な括弧列になるものを探します。これが (B) の操作です。
本番書いたコード
解法に自信がなかったので (A) の操作で l をだんだん進めていくような感じにしている(結局 2 回で終わるので while (1) とか書いてるのは意味がない)
int calc(int start, string s) { int cnt = start; for (char c : s) { if (c == '(') cnt++; else cnt--; if (cnt < 0) break; } return cnt; } class ParenthesesDiv1Easy { public: vector <int> correct(string s) { int n = s.size(); const vector<int> no = {-1}; if (n%2) return no; vector<int> ans; int ncnt = 0, l = 0; while (1) { if (calc(ncnt, s.substr(l)) >= 0) break; for (int i = n-1; i >= l; i--) { string t = s.substr(l, i-l+1); reverse(t.begin(), t.end()); for (char& c : t) { if (c == '(') c = ')'; else c = '('; } if (calc(ncnt, t) >= 0) { ans.push_back(l); ans.push_back(i); s = s.substr(0, l) + t + (i < n-1 ? s.substr(i+1) : ""); l = i+1; break; } } if (l==n) break; } cout << s << endl; if (calc(0, s) == 0) return ans; for (int r = n-1; r >= 1; r--) { string t = s.substr(r); reverse(t.begin(), t.end()); for (char& c : t) { if (c == '(') c = ')'; else c = '('; } t = s.substr(0, r) + t; if (calc(0, t) == 0) { ans.push_back(r); ans.push_back(n-1); return ans; } } return no; } };