読者です 読者をやめる 読者になる 読者になる

kmjp's blog

競技プログラミング参加記です

Codeforces #224 Div2. E. Ksenia and Combinatorics

コード量はそこまで多くないが、ややこしい問題。
いまだ正答数も少なめ。
http://codeforces.com/contest/382/problem/E

問題

数N・Kが与えられる。
1~Nの番号が振られた点からなり、1番の点を根とする二分木において、点の最大マッチング数がKとなるような根つき木グラフの組み合わせを列挙せよ。

解法

subtreeの状態としてdp[点の数][マッチング数][根を親の点とマッチングさせたいか否か]を取り、より小さな木から組み合わせ数をDPで求めていけばよい。

dp[x][y][0]及びdp[x][y][1]を求めるため、より小さなx,yの値から以下のように計算する。

  • 根が2つの子を持つ場合、2つのsubtreeの点の数L,Rを、それぞれ1~(x-2)、和がx-1となるように総当たりする。
    • まず根を除く(x-1)点の分け方として、2つの子の番号を {}_{x-1} C_2個選択し、かつそれ以下の点をどう2つの子に振り分けるか {}_{x-3} C_{L-1}通りある。
    • さらに、2つのsubtreeのマッチング数を総当たりする。
      • 2つのsubtreeの根がともにマッチング済みの場合、現在の根は親とマッチングを取りたい(コード中(dpdp[x][y][1] += pat*dpdp[l][lk][0]%mo*dpdp[r][rk][0];))
      • 2つのsubtreeの根のどちらか片方でもマッチングしてない根がある場合、現在の根とその根のマッチングをとり、マッチング数を1追加する(コード中(dpdp[x][y][0] += ~~ の3行)
  • 次に、根が1つの子をもつ場合を考える。
    • まずsubtreeの根の頂点の番号を(x-1)個から選択する。
      • subtreeの根がマッチング済みの場合、現在の根は親とマッチングを取りたい(コード中(if(y>0) dpdp[x][y][0] += (x-1)*dpdp[x-1][y-1][1]))
      • subtreeの根かマッチングしてないある場合、現在の根とその根のマッチングをとり、マッチング数を1追加する(コード中(dpdp[x][y][1] += (x-1)*dpdp[x-1][y][0];))

最終的な答えは、全体の根がさらにマッチングを求めていても求めていなくてもマッチング数がKに到達すればよいので、dp[N][K][0]+dp[N][K][1]になる。

ll mo=1000000007;
int N,K;
ll dpdp[51][51][2];

ll comb(int P_,int Q_) {
	static const int N_=1020;
	static ll C_[N_][N_];
	
	if(C_[0][0]==0) {
		int i,j;
		FOR(i,N_) C_[i][0]=C_[i][i]=1;
		for(i=1;i<N_;i++) for(j=1;j<i;j++) C_[i][j]=(C_[i-1][j-1]+C_[i-1][j])%mo;
	}
	if(P_<0 || P_>N_ || Q_<0 || Q_>P_) return 0;
	return C_[P_][Q_];
}

void solve() {
	int f,i,j,k,l,x,y;
	
	cin>>N>>K;
	
	dpdp[1][0][1]=1;
	
	for(x=2;x<=N;x++) FOR(y,K+1) { // x=num y=match
		// bintree
		for(l=1;l<=x-2;l++) {
			int r=x-1-l;
			ll pat=comb(x-1,2)*comb(x-3,l-1)%mo;
			
			for(int lk=0;lk<=y;lk++) {
				int rk=y-lk;
				dpdp[x][y][1] += pat*dpdp[l][lk][0]%mo*dpdp[r][rk][0];
				dpdp[x][y][1] %= mo;
			}
			
			for(int lk=0;lk<=y-1;lk++) {
				int rk=y-1-lk;
				dpdp[x][y][0] += pat*dpdp[l][lk][1]%mo*dpdp[r][rk][0];
				dpdp[x][y][0] += pat*dpdp[l][lk][0]%mo*dpdp[r][rk][1];
				dpdp[x][y][0] += pat*dpdp[l][lk][1]%mo*dpdp[r][rk][1];
				dpdp[x][y][0] %= mo;
			}
		}
		
		// monotree
		if(y>0) dpdp[x][y][0] += (x-1)*dpdp[x-1][y-1][1];
		dpdp[x][y][1] += (x-1)*dpdp[x-1][y][0];
		dpdp[x][y][0] %= mo;
		dpdp[x][y][1] %= mo;
	}
	
	cout << (dpdp[N][K][0]+dpdp[N][K][1])%mo << endl;
}

まとめ

最初親から順にマッチングを確定していったら、点が変に余って最大マッチングが取れなかった。
二分木の最大マッチングは葉から確定させればいいのか。

広告を非表示にする