TopCoder SRM 718 Div1 Easy InterleavingParenthesis、Div2 Medium InterleavingParenthesisDiv2

朝回なので不参加。EasyもMediumも簡単だったので出ておきたかった…。
https://community.topcoder.com/stat?c=problem_statement&pm=14635
https://community.topcoder.com/stat?c=problem_statement&pm=14642

問題

2つの括弧列S,Tが与えられる。
両文字列内の互いの相対位置を変えずにマージしたい。
マージの仕方のうち、正しい括弧の対応を満たすものは何通りか。

解法

以下を考える。
f(a,b) := Sのprefix a文字、Tのprefix b文字までを合わせてできる括弧列のうち、開き括弧より閉じ括弧の方が多いprefixがないものの組み合わせ総数。

f(0,0)=1から始め、f(|S|,|T|)を求めよう。
f(a,b)からf(a+1,b)とf(a,b+1)それぞれ、閉じ括弧の方が大きくならない場合に遷移すればよい。
f(a,b)の状態を考えると、先頭(a+b)文字の並び順に寄らず開き括弧と閉じ括弧の数は確定するので、a,b以外の情報を持つ必要はなくO(|S||T|)で解ける。

ll dp[2601][2601];
ll mo=1000000007;

class InterleavingParenthesis {
	public:
	int countWays(string s1, string s2) {
		int a=s1.size(),b=s2.size();
		vector<int> X,Y;
		X.push_back(0);
		Y.push_back(0);
		FORR(c,s1) X.push_back(X.back()+(c=='('));
		FORR(c,s2) Y.push_back(Y.back()+(c=='('));
		if((X.back()+Y.back())*2!=a+b) return 0;
		
		ZERO(dp);
		dp[0][0]=1;
		int i,j;
		FOR(i,a+1) FOR(j,b+1) {
			int num=(X[i]+Y[j])-((i+j)-(X[i]+Y[j]));
			if(i!=a) {
				if(s1[i]=='(' || num>0) (dp[i+1][j] += dp[i][j])%=mo;
			}
			if(j!=b) {
				if(s2[j]=='(' || num>0) (dp[i][j+1] += dp[i][j])%=mo;
			}
		}
		return dp[a][b];
	}
}

まとめ

225ptでもいいんじゃないかな…。