mayoko’s diary

プロコンとかいろいろ。

SRM 686 div1 easy: BracketSequenceDiv1

解法

制約からして半分全列挙だろと思い dp は考えませんでした(あとで dp 解書きます)。

前半部分で例えば " ( ( ) ( [ ] [ (" という文字列を取り出したら, 対応する括弧を取り除いて " ( ( [ ( " にします(" ( ] [ " の様に対応的にありえないものがあったらそれは無視する)。

で, 後半部分で対応する括弧を取り除いた後に " ) ] ) ) " となるものがあったら, 前計算していた " ( ( [ ( " の数だけ答えに加算する, という感じです。今回は空文字が許されていないので最後に答えから 1 を引きます。

下のコードでは map を使っているので非常に危ない(TLE, MLE 的な意味で)です。string を int に変換して int[] の形にするのが早いと思います。

class BracketSequenceDiv1 {
public:
    long long count(string s) {
        cout << "test" << endl;
        int n = s.size();
        int n1 = n/2, n2 = n-n1;
        map<string, int> m1;
        for (int i = 0; i < 1<<n1; i++) {
            string t;
            for (int j = 0; j < n1; j++) {
                if ((i>>j)&1) t += s[j];
            }
            bool ng = false;
            stack<char> st;
            for (char c : t) {
                switch (c) {
                    case '(':
                        st.push(c);
                        break;
                    case '[':
                        st.push(c);
                        break;
                    case ')':
                        if (st.empty() || st.top() != '(') {
                            ng = true;
                        } else {
                            st.pop();
                        }
                        break;
                    case ']':
                        if (st.empty() || st.top() != '[') {
                            ng = true;
                        } else {
                            st.pop();
                        }
                        break;
                }
            }
            if (ng) continue;
            string u;
            while (!st.empty()) {
                u += st.top();
                st.pop();
            }
            reverse(u.begin(), u.end());
            m1[u]++;
        }
        ll ans = 0;
        for (int i = 0; i < 1<<n2; i++) {
            string t, tar;
            for (int j = n-1; j >= n1; j--) {
                if ((i>>(j-n1))&1) t += s[j];
            }
            stack<char> st;
            bool ng = false;
            for (char c : t) {
                switch(c) {
                    case ')':
                        st.push(c);
                        break;
                    case '(':
                        if (st.empty() || st.top() != ')') {
                            ng = true;
                        } else {
                            st.pop();
                            break;
                        }
                        break;
                    case ']':
                        st.push(c);
                        break;
                    case '[':
                        if (st.empty() || st.top() != ']') {
                            ng = true;
                        } else {
                            st.pop();
                            break;
                        }
                        break;
                }
            }
            if (ng) continue;
            string u;
            while (!st.empty()) {
                u += st.top();
                st.pop();
            }
            reverse(u.begin(), u.end());
            for (char & c : u) {
                if (c == ')') c = '(';
                else if (c == ']') c = '[';
            }
            ans += m1[u];
        }
        return ans-1;
    }
};