けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

CS Academy 069 DIV2 C - Build Correct Brackets (最短経路数も一緒に求める最短路!)

まさにこれだったん。

CSA 069 DIV2 C Build Correct Brackets


()()))(())()
のようなカッコ列が与えられる。 最小回数flipして正しいカッコ列にせよ。 また最小回数flipで正しいカッコ列にする方法の数を数え上げよ。

・1 <= 文字列長 <= 2500


まさに最短路と一緒に最短路数も数え上げる問題。
正しい必要十分条件は、文字列を左から見ていって、

  • ‘(‘ の数 - ‘)’ の数

が常に 0 以上であること。 なので

dp[ i+1 ][ j ] := i 文字目まで見て、’(‘ の数 - ‘)’ の数が j となるような最小の flip回数
num[ i+1 ][ j ] := またそのような場合の数

として DP を組む。

#include <iostream>
using namespace std;

string str;

const long long MOD = 1000000007;
const long long INF = 1LL<<59;
long long dp[2600][2600];
long long num[2600][2600];

int main() {
    while (cin >> str) {
        for (int i = 0; i < 2600; ++i) {
            for (int j = 0; j < 2600; ++j) {
                dp[i][j] = INF;
                num[i][j] = 0;
            }
        }
        dp[0][0] = 0;
        num[0][0] = 1;
        for (int i = 0; i < str.size(); ++i) {
            for (int j = 0; j <= 2500; ++j) {
                if (str[i] == '(') {
                    // same
                    if (dp[i+1][j+1] > dp[i][j]) {
                        dp[i+1][j+1] = dp[i][j];
                        num[i+1][j+1] = num[i][j];
                    }
                    else if (dp[i+1][j+1] == dp[i][j]) {
                        num[i+1][j+1] += num[i][j];
                        num[i+1][j+1] %= MOD;
                    }
                    
                    // rev
                    if (j > 0) {
                        if (dp[i+1][j-1] > dp[i][j] + 1) {
                            dp[i+1][j-1] = dp[i][j] + 1;
                            num[i+1][j-1] = num[i][j];
                        }
                        else if (dp[i+1][j-1] == dp[i][j] + 1) {
                            num[i+1][j-1] += num[i][j];
                            num[i+1][j-1] %= MOD;
                        }
                    }
                }
                else {
                    // same
                    if (j > 0) {
                        if (dp[i+1][j-1] > dp[i][j]) {
                            dp[i+1][j-1] = dp[i][j];
                            num[i+1][j-1] = num[i][j];
                        }
                        else if (dp[i+1][j-1] == dp[i][j]) {
                            num[i+1][j-1] += num[i][j];
                            num[i+1][j-1] %= MOD;
                        }
                    }
                    
                    // rev
                    {
                        if (dp[i+1][j+1] > dp[i][j] + 1) {
                            dp[i+1][j+1] = dp[i][j] + 1;
                            num[i+1][j+1] = num[i][j];
                        }
                        else if (dp[i+1][j+1] == dp[i][j] + 1) {
                            num[i+1][j+1] += num[i][j];
                            num[i+1][j+1] %= MOD;
                        }
                    }
                }
            }
        }
        
        cout << dp[str.size()][0] << " " << num[str.size()][0] << endl;
    }
}