WARush

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

SRM686 Div1 Easy "BracketSequenceDiv1"

解法

区間dpる。

dp[L][R] := LからRまでの区間にて、シーケンスをcorrectにする消し方の場合の数
初期化

L == Rの場合、その一文字を消すしかcorrectにする方法はないので1

更新

Rのカッコに着目し、こいつを追加したときにどうやって更新するか考える。
まず、Rのカッコが"("や"["だった場合、これは消すしかcorrectにする方法がないので消すことにする。
すると、dp[L][R] = dp[L][R - 1]となる。
Rのカッコが")"や"]"だった場合、まず消す場合は同様にdp[L][R - 1]パターンでcorrectにできる。
それから、LからR - 1の間の"("か"["のカッコとペアを作ることが出来るため、消さないで残す方法があることになる。
ペアとするカッコのインデックスをiとすると、Lからi - 1, i + 1からR - 1それぞれでパターンを作ることができるので、それらを掛け合わせたdp[L][i - 1] * dp[i + 1][R - 1]だけcorrectにできる。
下図を見て欲しい。
f:id:Ekaing:20160928235352p:plain
図は、Rのカッコをindex4のカッコとペアにするぞ!!と意気込んでいる状態である。
すると、黄色の部分と緑の部分がそれぞれ独立してパターンを作ることができるので、dp[1][3] * dp[5][6]がdp[1][7]に足しこまれるという感じ。

ペアとするカッコはLからR - 1までを走査して、どんどん足しこんでく。

結果

dp[0][n - 1] - 1
※全部消すのはNGだ!

事後

Editorialのソースコードの簡潔さよ・・・

ソースコード

long long dp[45][45];

class BracketSequenceDiv1 {
    public:
    long long count(string s) {

        int n = s.size();

        for (int len = 1; len <= n; len++) {
            for (int L = 0; L <= n - len; L++) {
                int R = L + len - 1;
                if (len == 1) {
                    // 長さ1のところは消すの1パターン
                    dp[L][R] = 1;
                } else {
                    if (s[R] == '(' || s[R] == '[') {
                        // 消すしかない!
                        dp[L][R] = dp[L][R - 1];
                    } else {
                        // 消す!
                        dp[L][R] = dp[L][R - 1];
                        // ペアを順に探していく
                        char pair = s[R] == ')' ? '(' : '[';
                        for (int i = L; i < R; i++) {
                            if (s[i] == pair) {
                                // 1つ目のサブセット
                                int L1 = i + 1;
                                int R1 = R - 1;
                                long long sub1 = L1 <= R1 ? dp[L1][R1] : 1;
                                // 2つ目のサブセット
                                int L2 = L;
                                int R2 = i - 1;
                                long long sub2 = L2 <= R2 ? dp[L2][R2] : 1;

                                dp[L][R] += sub1 * sub2;
                            }
                        }
                    }
                }
            }
        }

        return dp[0][n - 1] - 1;
    }
};