Codeforces #343 Div2. C. Famil Door and Brackets

またBで誤読によるWA+タイムロスをやらかすも、Eがさっくり解けたおかげで良い順位。おかげで初めてwriterの記事で名前が出た。
http://codeforces.com/contest/629/problem/C

問題

開き括弧・閉じ括弧からなるN文字の有効文字列(開き括弧と閉じ括弧の対応が取れている文字列)を作りたい。
うち、M文字分の部分文字列sが指定されている。
これらの頭に文字列p、後ろにqを付与し、文字列(p+s+q)が全体でN文字の有効文字列となるようにしたい。
p,qの組み合わせは何通りか。

解法

Nは大きいが、N-Mは高々2000。よってp,qも2000文字以下である。
まずpの候補として、DPで以下を求めよう。
dp(a,b) := a文字の文字列で、prefixが常に閉じ括弧の数が開き括弧の数以下で、かつ全体で開き括弧の方がb個多い者の組み合わせ数
同様にqの候補として以下を考えるが、対称性よりdp=dp2なので２回同じDPを行う必要はない。
dp2(a,b) := a文字の文字列で、suffixが常に開き括弧の数が閉じ括弧の数以下で、かつ全体で閉じ括弧の方がb個多い者の組み合わせ数

s全体で開き括弧の数がどう変わるか、最初と最後の差分及び、pを処理した段階で最低何個開き括弧を持っていれば、(p+s)のprefixが途中閉じ括弧の方が多くなることがないか求めよう。
例えばs全体で、(開き括弧-閉じ括弧)の数がd、またprefixのうち閉じ括弧の方が最大m個多い場合があるとする。

pとしてdp(a,b)に相当するものを選んだとする。
a≦N-M、b≧mであれば、(p+s)のprefixが閉じ括弧の方が多くなるものがなく、全体で有効文字列となるにはqとしてdp2(N-M-a,b+d)となるものを選べばよい。

すなわちa≦N-M、b≧mを満たす(a,b)に対し、dp(a,b)*dp2(N-M-a,b+d)の総和を取るとそれが解。

int N,M;
string S;
ll pre[2020][2020];
ll post[2020][2020];
ll mo=1000000007;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M>>S;
	
	pre[0][0]=1;
	FOR(i,2010) {
		FOR(j,2010) if(pre[i][j]) {
			(pre[i+1][j+1]+=pre[i][j])%=mo;
			if(j) (pre[i+1][j-1]+=pre[i][j])%=mo;
		}
	}
	
	int dif=0,mi=0;
	FORR(c,S) {
		if(c=='(') dif++;
		else dif--, mi=min(mi,dif);
	}
	
	ll ret=0;
	for(i=0;i<=N-M;i++) {
		FOR(j,2010) if(pre[i][j] && j+mi>=0) {
			x=j+dif;
			y=N-M-i;
			if(x<=y) (ret += pre[i][j]*pre[y][x])%=mo;
		}
	}
	cout<<ret<<endl;
}

まとめ

この開き括弧と閉じ括弧の対応関係が取れた文字列、決まった言い方ないのかな。
validと言ってみたり「(角括弧で)bracket sequence」と言ってみたり、言い方が色々あって面倒。