TopCoder SRM 517 Div1 Medium AdjacentSwaps

これは基本的なアイデアにはたどり着いたけど、最後までは自力で到達できず他のコードを参考にした。
http://community.topcoder.com/stat?c=problem_statement&pm=11537

問題

初期状態で0～(N-1)が配置された数列Pがある。
ここで、P[i]とP[i+1]を入れ替える、という処理を0 ≤ i < N-1について1回ずつ計N-2回行った。

得られた結果が与えられるPとなるような入れ替え処理の順番の組み合わせ数を求めよ。

解法

数字の位置より、入れ替えの順序性を規定できる。

例えば以下のように2が3つ右に移動したとする。

* * 2 * * * * *
↓
* * * * * 2 * *

この時、以下の順序性が成り立つ。

• P[2]とP[3]の入れ替えはP[1]とP[2]より前
• P[2]とP[3]の入れ替えはP[3]とP[4]より前
• P[3]とP[4]の入れ替えはP[4]とP[5]より前
• P[4]とP[5]の入れ替えはP[4]とP[5]より後

後はDPでL番目～R番目の区間の並べ替えをメモ付再帰で行えばよい。
L～R番目中の各xにおいて、上記順序性より最初に行っていいのであればそれを行い、後はL～x-1及びx+1～Rでの処理の積およびその選択順()の積を加えていけばよい。

ll mo=1000000007;
const int CN=51;
ll C[CN][CN];

class AdjacentSwaps {
	public:
	ll dpdp[51][51];
	int dir[51][51];
	int N;
	ll dodo(int L,int R) {
		int x,y;
		if(L>=R) return 1;
		if(dpdp[L][R]>=0) return dpdp[L][R];
		dpdp[L][R]=0;
		
		for(x=L;x<=R;x++) {
			for(y=L;y<=R;y++) if(dir[y][x]) break;
			if(y==R+1) dpdp[L][R]+=C[R-L][x-L]*dodo(L,x-1)%mo*dodo(x+1,R)%mo;
		}
		dpdp[L][R]%=mo;
		return dpdp[L][R];
	}
	
	int theCount(vector <int> p) {
		int i,j,y,x,tot=0;
		N=p.size();
		
		FOR(x,CN) C[x][0]=C[x][x]=1;
		for(i=1;i<CN;i++) for(j=1;j<i;j++) C[i][j]=(C[i-1][j-1]+C[i-1][j])%mo;
		
		ZERO(dir);
		MINUS(dpdp);
		FOR(i,N) {
			j=i-p[i];
			if(j==0) return 0;
			if(j>0) {
				if(p[i]>0) dir[p[i]][p[i]-1]=i+1;
				for(x=p[i];x<i-1;x++) dir[x][x+1]=i+1;
				if(i<N-1) dir[i][i-1]=i+1;
			}
			else {
				if(p[i]<N-1) dir[p[i]-1][p[i]]=i+1;
				for(x=p[i];x>i+1;x--) dir[x-1][x-2]=i+1;
				if(i>0) dir[i-1][i]=i+1;
			}
		}
		FOR(i,N-1) FOR(x,N-1) FOR(y,N-1) dir[x][y]|=dir[x][i]&&dir[i][y];
		FOR(x,N-1) FOR(y,N-1) if(dir[x][y] && dir[y][x]) return 0;
		return dodo(0,N-2);
		
	}
}

まとめ

面白い問題だった。