hogecoder

tsutaj 競技プログラミングの記録

TopCoder SRM 718 Div1 Easy (Div2 Med): InterleavingParenthesis

するめうめ

tsutaj.hatenablog.com

問題概要

原文 → TopCoder Statistics - Problem Statement

括弧列  S_1 S_2 が与えられる。

 S_1 S_2 の各文字を、 S_2 の文字間の相対位置関係を変えずに挿入することを考える。このとき、 valid な括弧列になるパターンは何通りあるか?ただし、文字として同じであっても、もともと  S_1 の文字であったか  S_2 の文字であったかは区別される。

解説

まず、ここでいう valid な括弧列  S とは、'(' を  +1 と、 ')' を  -1 と見たとき、以下と同値です。

  • 全要素の総和が  0
  • 先頭からの累積和が一度も負にならない

したがって、 S_1 の累積和と  S_2 の累積和の和を取った時に  0 でなければ、どう並べても valid な括弧列は作れません。

さて、  S_1 i 文字目、 S_2 j 文字目までを既に使用したとしましょう。この後の文字を適切に並べることで valid な括弧列を作れるかどうかの判定は、累積和が非負であるかどうかで可能です。

先ほどの状態から  1 つ進んだ状態、すなわち  S_1 または  S_2 から新たに  1 文字使うことを考えましょう。ここでの valid な括弧列判定も、やはり累積和で行えます。

ここまで来ると  \mathrm{dp} \left[ i \right] \left[ j \right] :=  S_1 i 文字目、 S_2 j 文字目までを使用したときの valid になる可能性のある括弧列の総数 という DP が構成でき、  O(|S_1| |S_2|) で解くことができます。

ソースコード

class InterleavingParenthesis {
    public:
    int sum1[2510], sum2[2510];
    int dp[2510][2510];
    int d1[2] = {1, 0};
    int d2[2] = {0, 1};
    int countWays(string s1, string s2) {
        int N = s1.length(), M = s2.length();
        memset(sum1, 0, sizeof(sum1));
        memset(sum2, 0, sizeof(sum2));
        for(int i=0; i<N; i++) {
            sum1[i+1] = sum1[i] + (s1[i] == '(' ? 1 : -1);
        }
        for(int i=0; i<M; i++) {
            sum2[i+1] = sum2[i] + (s2[i] == '(' ? 1 : -1);
        }
        if(sum1[N] + sum2[M] != 0) return 0;

        memset(dp, 0, sizeof(dp));
        dp[0][0] = 1;
        for(int i=0; i<=N; i++) {
            for(int j=0; j<=M; j++) {
                int cur_sum = sum1[i] + sum2[j];
                if(cur_sum < 0) continue;

                for(int k=0; k<2; k++) {
                    int ni = i + d1[k], nj = j + d2[k];
                    if(ni > N || nj > M) continue;
                    int nxt_sum = sum1[ni] + sum2[nj];
                    if(nxt_sum < 0) continue;
                    (dp[ni][nj] += dp[i][j]) %= MOD;
                }
            }
        }
        return dp[N][M];
    }
};