mayoko’s diary

プロコンとかいろいろ。

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;
    }
};