CSAcademy Round #24 : D. BST Fixed Height

今回は時間を間違えて不参加でした。
https://csacademy.com/contest/round-24/#task/bst-fixed-height

問題

整数N,Hが与えられる。
二分木のうち高さがH、頂点数がNのものはいくつあるか。

解法

上から何段目に何個頂点があり、あと何個頂点を配置する、というDPでも解にはたどり着けるが、O(H*N^3)となりTLEする。

以下を考える。求めたいのはF(N,H)である。
F(n,h) := 高さh、頂点n個の二分木の数

以下は明確である。

• F(0,0)=0
• F(1,0)=1
• F(0,1)=0

以下残りのケース、n,hともに正である場合を考える。
まず根には当然頂点が1個なければならない。
求めるのは以下の和である。

• 左の子頂点のSubTreeの高さと右の子頂点のSubTreeの高さがともに(h-1)段
• 左の子頂点のSubTreeの高さが(h-1)段で、右の子頂点のSubTreeの高さがともに(h-2)段以下
• 右の子頂点のSubTreeの高さが(h-1)段で、左の子頂点のSubTreeの高さがともに(h-2)段以下

G(n,h) := sum(F(n,j)) (0≦j≦h)とする。
そうすると上記3値はそれぞれ以下に相当する。

• 
• 
• 

これはメモ化再帰でO(H*N^2)で解ける。

int N,H;
int mo=1000000007;
ll memo[505][505];
ll memo2[505][505];

ll dpdp2(int n,int h);

ll dpdp(int n,int h) {
	if(h==1) return n==1;
	if(h<=0) return 0;
	if(n<h) return 0;
	if(memo[n][h]>=0) return memo[n][h];
	ll ret=0;
	
	int i;
	for(i=h-1;i<=n-1;i++) ret+=2*dpdp(i,h-1)*dpdp2(n-1-i,h-2)%mo;
	for(i=h-1;n-1-i>=h-1;i++) ret+=dpdp(i,h-1)*dpdp(n-1-i,h-1)%mo;
	return memo[n][h]=ret%mo;
}

ll dpdp2(int n,int h) {
	if(n==0) return 1;
	if(n<0 || h<0) return 0;
	if(memo2[n][h]>=0) return memo2[n][h];
	memo2[n][h]=(dpdp(n,h)+dpdp2(n,h-1))%mo;
	return memo2[n][h];
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>H;
	MINUS(memo);
	MINUS(memo2);
	cout<<dpdp(N,H)<<endl;
}

まとめ

自力でさっと計算量落とせなかった…。