AtCoder AGC #030 : F - Permutation and Minimum

これも1600ptの割に簡単に思えるが、本番じゃ解けなさそう。
https://atcoder.jp/contests/agc030/tasks/agc030_f

問題

1～2NのPermutation Aを考える。
入力で一部の値は指定されている。

ここから、(0-originで)B[i]=min(A[2*i],A[2*i+1])で生成されるPermutation Bを考える。
Bとしてあり得るものは何通りか。

解法

入力値から、(A[2*i],A[2*i+1])の対は以下の３通りに分類できる。

1. 両方とも決まっている。この場合B[i]も確定する。
2. 両方とも決まっていない。
3. 片方決まっている。

ここで、n=1～2Nが以下のどこに分類されるかを考える。

• a. nがBに現れずAでも指定されない。
• b. nがBに現れず、Aでは指定される。
• c. 上記1のパターンの片割れとしてBに現れる
• d. 上記2のパターンの片割れとしてBに現れる
• e. 上記3のパターンの片割れ(決まってない方)としてBに現れる

nがそれぞれどこに分類されるか、が異なると生成されるBは異なる。
2N～1まで降順に、以下の値を求めよう。
f(n, x, y) := 2N～(n+1)まで定めたとき、まだペアの定まっていないa.に相当する数がx個、b.に相当する数がy個

nの配置を決めるとき、上記５分類のどれになるかでx,yの増減を考えていく。

int N;
int L;
int used[606];
ll dp[606][306][306];
ll mo=1000000007;


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	L=2*N;
	
	int F=0;
	FOR(i,N) {
		cin>>x>>y;
		if(x>y) swap(x,y);
		
		if(y==-1) {
			F++;
		}
		else if(x==-1 && y!=-1) {
			used[y]=1;
		}
		else if(x>-1) {
			used[x]=used[y]=2;
		}
	}
	
	dp[L][0][0]=1;
	for(i=L;i>=1;i--) FOR(x,N+1) FOR(y,N+1) {
		ll v=dp[i][x][y];
		if(v==0) continue;
		
		if(used[i]==2) {
			(dp[i-1][x][y]+=v)%=mo;
		}
		else if(used[i]==1) {
			(dp[i-1][x][y+1]+=v)%=mo;
			if(x) (dp[i-1][x-1][y]+=v)%=mo;
		}
		else {
			(dp[i-1][x+1][y]+=v)%=mo;
			if(x) (dp[i-1][x-1][y]+=v)%=mo;
			if(y) (dp[i-1][x][y-1]+=v*y)%=mo;
		}
	}
	
	ll ret=dp[0][0][0];
	while(F) ret=ret*(F--)%mo;
	cout<<ret<<endl;
	
}

まとめ

実装は軽いんだよな。