するめうめ
問題概要
原文 → TopCoder Statistics - Problem Statement
括弧列 と が与えられる。
に の各文字を、 の文字間の相対位置関係を変えずに挿入することを考える。このとき、 valid な括弧列になるパターンは何通りあるか?ただし、文字として同じであっても、もともと の文字であったか の文字であったかは区別される。
解説
まず、ここでいう valid な括弧列 とは、'(' を と、 ')' を と見たとき、以下と同値です。
- 全要素の総和が
- 先頭からの累積和が一度も負にならない
したがって、 の累積和と の累積和の和を取った時に でなければ、どう並べても valid な括弧列は作れません。
さて、 の 文字目、 の 文字目までを既に使用したとしましょう。この後の文字を適切に並べることで valid な括弧列を作れるかどうかの判定は、累積和が非負であるかどうかで可能です。
先ほどの状態から つ進んだ状態、すなわち または から新たに 文字使うことを考えましょう。ここでの valid な括弧列判定も、やはり累積和で行えます。
ここまで来ると の 文字目、 の 文字目までを使用したときの valid になる可能性のある括弧列の総数 という DP が構成でき、 で解くことができます。
ソースコード
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]; } };