Topcoder SRM 718 Div1 Easy - InterleavingParenthesis

これまで全然やっていなかったSRMの過去問埋めをぼちぼちやっていこうという気持ちになりまして、せっかくだから解いた問題に関しては記録をつけていこうと思います。当面はDiv1 Easyを新しいものからやっていく予定です。この1回で飽きる可能性もありますがその時は察してください。記事の形式はkmjpさんのブログの影響をめちゃめちゃ受けています(僕はkmjpさんのブログをめちゃめちゃ見過ぎているので)。

問題概要

開き括弧と閉じ括弧の2種類の文字のみからなる文字列s1, s2が与えられる。次の操作を行って得られる文字列のうち、括弧の対応が正しくなるものは何通りか。

操作: s1, s2のうち空でないものをひとつ選び、選んだ方の先頭の文字を削除して新文字列の末尾に加える。これを両方の文字列が空になるまで続ける。

|s1| <= 2500, |s2| <= 2500

解法

dp[i][j] = s1をi文字目、s2をj文字目まで見たときの文字の取り方 としてdp.

遷移を考えると(s1から何文字取ったか, s2から何文字取ったか, 開かれている括弧の数)でdpしたくなるが、それだと25003で間に合わない。よくよく考えると何文字目まで見たかがわかってるなら開かれ括弧の数は一意に定まるので状態として持つ必要はなく、結局s1, s2から何文字取ったかの2つだけ見ればよいことがわかってO(|S|^2)。

遷移はこんな感じでやった

  • 開かれ括弧が0より多い → 開き括弧も閉じ括弧も取れる
  • 開かれ括弧がちょうど0 → 開き括弧しか取れない
  • 開かれ括弧が0より少ない → 取れない

感想

解けてみれば至って普通のdpなんですが、3乗から2乗に落とすのにちょっと困ってしまいました。

コード (C++)

const ll MOD = 1000000007;

class InterleavingParenthesis {
    public:
    int countWays(string s1, string s2) {
        int N = s1.size();
        int M = s2.size();
        vector<int> A(N + 1, 0);
        vector<int> B(M + 1, 0);
        REP(i, N) A[i + 1] = A[i] + (s1[i] == '(');
        REP(i, M) B[i + 1] = B[i] + (s2[i] == '(');
        cout << A[N] << " " << B[M] << endl;

        if ((A[N] + B[M]) * 2 != N + M) return 0;


        vector<vector<ll>> dp(N + 1, vector<ll>(M + 1, 0));
        dp[0][0] = 1;

        REP(i, N + 1) REP(j, M + 1) {
            int open = A[i] + B[j] - (i + j - A[i] - B[j]);
            if (open > 0) {
                if (i < N) (dp[i + 1][j] += dp[i][j]) %= MOD;
                if (j < M) (dp[i][j + 1] += dp[i][j]) %= MOD;
            } else if (open == 0) {
                if (i < N && s1[i] == '(') (dp[i + 1][j] += dp[i][j]) %= MOD;
                if (j < M && s2[j] == '(') (dp[i][j + 1] += dp[i][j]) %= MOD;
            }
        }

        return dp[N][M];
    }
};