WARush

SRMの結果とか、解けた問題のコードを書いていきます

SRM688 Div1 Easy "ParenthesesDiv1Easy"

解法

こちらを参考にしましたm(_ _)m
mayokoex.hatenablog.com

参考先でも言っているように、開きカッコ閉じカッコのペアが成立しているものを取り除いていくと、最終的には「))))((」とか「)(((((」とか「)))))))」とかになる。これを「((()))」とするためには高々2回フリップを使えばよい。最初に取り除いたカッコたちについては、フリップしたところでペアが成立することは変わらないので無視しても大丈夫。

事後

こうゆうちょっとした発想が必要な問題が解けるようになりたいなぁ・・

ソースコード

class Elm {
    public:
    int id;
    char c;

    Elm(int id, int c) {
        this->id = id;
        this->c = c;
    }
};

class ParenthesesDiv1Easy {
    public:
    vector<int> correct(string s) {
        int n = s.size();

        // 奇数だったら無理
        if (n % 2 != 0) {
            vector<int> ans;
            ans.push_back(-1);
            return ans;
        }

        // ペアが成立したカッコは無視し、それ以外のカッコとそのindexを保持
        vector<Elm> ps;
        for (int i = 0; i < n; i++) {
            if (s[i] == ')' && !ps.empty() && ps.back().c == '(') {
                ps.pop_back();
            } else {
                ps.push_back(Elm(i, s[i]));
            }
        }

        // フリップすべきindexを算出
        int m = ps.size();
        int close_L_id = -1;
        int close_R_id = -1;
        int open_L_id = -1;
        int open_R_id = -1;
        for (int i = 0; i < m; i++) {
            if (ps[i].c == ')') {
                if (close_L_id == -1) {
                    close_L_id = ps[i].id;
                }
                if (i < m / 2) {
                    close_R_id = ps[i].id;
                }
            } else {
                if (open_L_id == -1 && m / 2 <= i) {
                    open_L_id = ps[i].id;
                }
                open_R_id = ps[i].id;
            }
        }

        // 答えを設定
        vector<int> ans;
        if (close_L_id != -1) {
            ans.push_back(close_L_id);
            ans.push_back(close_R_id);
        }
        if (open_L_id != -1) {
            ans.push_back(open_L_id);
            ans.push_back(open_R_id);
        }
        return ans;
    }
};