Codeforces Round #343 (Div. 2) C. Famil Door and Brackets

問題

codeforces.com

解法

dp[now][d] = (now 個の括弧を使った文字列の内, '(' の数が ')' の数を下回ることが一度もなく, '(' の数が now までで ')' の数を d 個上回っているようなものの数) とします。これは簡単な dp で計算できますね。

で, 入力文字列 s について, minDiff = ('(' の数) - (')' の数) を各 prefix について見ていった時の最小値
diff = ('(' の数) - (')' の数) を s の最後まで見ていった時の値
というのを計算しておきます。

s に対して, 左側の文字列の数を left, '(' の数が ')' の数を上回っている数を d としましょう。このとき, d+minDiff < 0 だと, 途中で ')' の数が多くなりすぎるので NG です。他の場合は, 右側の文字列を使って余分な '(' を ')' で対処させればよいですが, この場合の数は, 文字列の長さを right として, dp[right][d+diff] で書けます。

const ll MOD = 1e9+7;
ll dp[2222][2222];

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n, m;
    cin >> n >> m;
    string s;
    cin >> s;
    int minDiff = 0, diff = 0;
    for (int i = 0; i < m; i++) {
        if (s[i] == '(') diff++;
        else diff--;
        minDiff = min(minDiff, diff);
    }
    dp[0][0] = 1;
    int l = n-m;
    for (int now = 0; now < l; now++) for (int d = 0; d <= now; d++) {
        (dp[now+1][d+1] += dp[now][d]) %= MOD;
        if (d > 0) (dp[now+1][d-1] += dp[now][d]) %= MOD;
    }
    ll ans = 0;
    for (int left = 0; left <= l; left++) {
        int right = l-left;
        for (int d = 0; d <= left; d++) {
            if (d+minDiff < 0) continue;
            if (d+diff <= right) (ans += dp[left][d] * dp[right][d+diff] % MOD) %= MOD;
        }
    }
    cout << ans << endl;
    return 0;
}