WARush

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

SRM686 Div2 Hard "BracketSequenceDiv2"

解法

連続しない部分文字列の数え上げなので、基本的には以下のやり方で。
ekaing.hatenablog.com

あとは、最終的に全ての左カッコに右カッコのペアが出来ていなければならないので、超過した左カッコの数を記録しておく。

事後

難しいなぁ・・・

ソースコード

const long long MOD = 1000000007LL;
long long dp[110][110];

class BracketSequenceDiv2 {
    public:
    int count(string s) {
        s += "D"; // ダミー
        int n = s.size();

        // dp初期化
        memset(dp, 0, sizeof(dp));
        for (int i = 0; i < n; i++) {
            if (s[i] == '(') dp[i][1] = 1;
        }

        // dp更新
        int open_pre_pos = -1; // iから見て左側最寄りの'('の位置
        int close_pre_pos = -1; // iから見て左側最寄りの')'の位置
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                int m = j;
                if (s[i] == '(') m--;
                if (s[i] == ')') m++;
                if (m < 0 || n < m) continue;

                // open
                if (open_pre_pos != -1) {
                    dp[i][j] += dp[open_pre_pos][m];
                    dp[i][j] %= MOD;
                }
                // close
                if (close_pre_pos != -1) {
                    dp[i][j] += dp[close_pre_pos][m];
                    dp[i][j] %= MOD;
                }
            }
            if (s[i] == '(') open_pre_pos = i;
            if (s[i] == ')') close_pre_pos = i;
        }

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