SRM688 ParenthesesDiv1Easy
https://community.topcoder.com/stat?c=problem_statement&pm=14229
苦戦しました……。
本番では問題文を完全に誤読し涙の嘘貪欲。
概要はというと、与えられた括弧列に対し、ある区間を指定し順序反転&かっこの向き反転という操作を繰り返して「正しい括弧列」にしろ、というもの。正しい括弧列というのは初見でしたが頻出らしく、必ずペアになったかっこが向かい合っているというもの。'('を+1,')'を-1として高さを計算すると条件は以下のようになります。
http://www.slideshare.net/chokudai/mujin2016
↑このスライドから画像をお借りします。
解法。長さが奇数なら無理。偶数なら必ず三手以内で反転できます。'('を+1,')'を-1として高さを計算し、この値を2xとします(値の差が2なので必ず2の倍数になります)。続いて、高さがxとなる箇所で右側を反転すると、右側の文字列の高さが-xになり、全体の高さは0になります。つまり括弧の数がそろいます。あとは高さが最小値をとるところで左右両方の文字列に対し操作を行います。こうすると、高さが負になる部分がなくなるので正しい括弧列になります。上の画像の折れ線グラフが負になっているところがあったら反転する、くらいの感じです。
class ParenthesesDiv1Easy { public: vector<int> correct(string s) { int n = s.size(), sum = 0; vector<int> ans; if(n % 2){ ans.push_back(-1); return ans; } for(char a : s) sum += (a == '(') ? 1 : -1; int k = sum / 2; rep(i, n){ if(s[i] == '(') k--; else k++; if(k == 0 && i != n - 1){ ans.push_back(i + 1); ans.push_back(n - 1); break; } } if(ans.size()){ string sb = s.substr(ans[0]); s.erase(ans[0]); string rsb = ""; for(char a : sb) rsb += a == '(' ? ")" : "("; reverse(rsb.begin(), rsb.end()); s += rsb; } sum = 0; int minsum = INF, mi; rep(i, n){ sum += (s[i] == '(') ? 1 : -1; if(sum < minsum){ minsum = sum; mi = i; } } if(mi == n - 1) return ans; ans.push_back(0); ans.push_back(mi); ans.push_back(mi + 1); ans.push_back(n - 1); return ans; } };
考察ゲーで行き詰まるとすぐ愚直解に逃げるクセがあり、よくありません。頭が悪いからこそしっかり考えないといけないのに。反省。