New Year Contest 2015 : I - マージ

本番結構苦戦したけど何とか解けた。
http://nyc2015.contest.atcoder.jp/tasks/nyc2015_9

問題

1～Nのpermutationである２つの数列P,Qがある。
２つの数列のいずれかの先頭要素を取り出し、Rに加えるという処理を繰り返し、2N要素の数列Rを作る。
あり得るRの組み合わせ数を求めよ。

解法

P[p..(N-1)]とQ[q..(N-1)]から生成できる数列F(p,q)及び数列の数G(p,q)をメモ化再帰で求めていく。

P[p]!=Q[q]なら話は簡単で、P[p]にF(p+1,q)を連結したものとQ[q]にF(p,q+1)を連結したものが考えられ、これらは明らかに異なる数列なので、G(p,q)=G(p+1,q)+G(p+1,q)である。

P[p..(N-1)]とQ[q..(N-1)]の先頭x-1文字が等しく、x文字目で初めて異なる場合を考える。
すなわちP[p]=Q[q]、P[p+1]=Q[q+1]、…、P[p+x-1]=Q[q+x-1]、P[p+x]!=Q[q+x]の場合である。

ここで以下のような関数R(x,y)を考える。
R(x,y)は片方の数列からx個、もう片方からy個とるが、最後の状態に至るまで前者の方が常に数多く撮った状態を保つような取り方である。（最後はx==yでもよい）
これは簡単にDPで求められて、以下の通りである。

• x＜yならR(x,y)=0
• x≧yならR(x,y)=R(x,y-1)+R(x-1,y)

もとのG(p,q)に戻る。
x文字以内のi文字を、PとQから同数取る場合はR(i,i)*G(p+i,q+i)通りとなる。
また、PとQどちらかが先に固有の値P[p+x]またはQ[q+x]にたどり着くケースである以下の値を足しこめば良い。

• 先にP[p+x]にたどり着くケースが
• 先にQ[q+x]にたどり着くケースが

上記処理をDPで行い、最終的にG(0,0)が答え。

int N;
int P[2001],Q[2001];
ll mo=1000000007;
ll memo[2005][2005];

ll dp[2005][2005];

ll dodo(int p,int q) {
	if(p>N || q>N) return 0;
	if(p==N || q==N) return 1;
	ll& ret=memo[p][q];
	if(ret>=0) return ret;
	ret=0;
	if(P[p]!=Q[q]) return ret=(dodo(p+1,q)+dodo(p,q+1))%mo;
	int x,i;
	for(x=1;x<N;x++) {
		if(p+x>=N || q+x>=N) break;
		if(P[p+x]!=Q[q+x]) break;
	}
	for(i=1;i<=x;i++) ret+=dp[i][i]*dodo(p+i,q+i)%mo;
	if(p+x<N) for(i=0;i<x;i++) ret+=dp[x][i]*dodo(p+x+1,q+i)%mo;
	if(q+x<N) for(i=0;i<x;i++) ret+=dp[x][i]*dodo(p+i,q+x+1)%mo;
	ret %= mo;
	
	return ret;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	dp[0][0]=dp[1][0]=1;
	FOR(x,2003) FOR(y,x) {
		dp[x+1][y]=(dp[x+1][y]+dp[x][y])%mo;
		dp[x][y+1]=(dp[x][y+1]+dp[x][y])%mo;
	}
	
	cin>>N;
	FOR(i,N) cin>>P[i],P[i]--;
	FOR(i,N) cin>>Q[i],Q[i]--;
	MINUS(memo);
	cout<<dodo(0,0)<<endl;
}

まとめ

ややこしいDPだが自力で解けて良かった。