mayoko’s diary

プロコンとかいろいろ。

SRM 670 div1 easy:Bracket107

寝坊したので SRM 670 は不参加でした。

解法

実は条件を満たすような LCS の最大値は文字列 s の長さを n として必ず n-1 であることがわかります。これは, 以下の場合分けを考えることによりわかります。
s が (())()()のように2つ以上の Correct Bracket の場合は s は A(B) という形になります。この時は, 文字列として (AB) という文字列を作れば LCS の大きさは n-1 になります。
s が 1 つにまとまった Correct Bracket の場合は s は (A) という形になります。この時は, 文字列として A() という文字列を作れば LCS の大きさは n-1 になります。

ということで, LCS の大きさの最大値は n-1 です。なので, 元の文字列から 1 文字抜き取った文字列に '(' か ')' を挿入して, それが Correct Bracket になるなら答えに加算していく, ということをやれば OK です。

bool check(string s) {
    stack<char> st;
    for (char c : s) {
        if (c == '(') st.push(c);
        else {
            if (st.empty()) return false;
            st.pop();
        }
    }
    return st.empty();
}

class Bracket107 {
public:
    int yetanother(string s) {
        set<string> S;
        int n = s.size();
        for (int i = 0; i < n; i++) {
            string t;
            for (int j = 0; j < n; j++) {
                if (j == i) continue;
                t += s[j];
            }
            if (check("("+t)) S.insert("("+t);
            for (int j = 0; j < n-1; j++) {
                for (int f = 0; f < 2; f++) {
                    string nt;
                    for (int k = 0; k <= j; k++) {
                        nt += t[k];
                    }
                    if (f == 0) nt += "(";
                    else nt += ")";
                    for (int k = j+1; k < n-1; k++) nt += t[k];
                    if (check(nt)) S.insert(nt);
                }
            }
        }
        return S.size()-1;
    }
};