kmjp's blog

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

CSAcademy Round #14 : E. Bounded Diameter Trees

本番終わり際に方針が立ったけど間に合わなかった。
https://csacademy.com/contest/round-14/#task/bounded-diameter-trees

問題

N頂点の根付き木を考える。
1番の頂点を根とし、以降の頂点は自身より若い番号の頂点を親に持つ。

そのようにしてできる木をなすグラフにおいて、直径がM以下となるものの数を求めよ。

解法

以下の2値を考える。
f(n,d) := n頂点の根付き木で、そこからの木の深さの最大値がちょうどdであり、かつ直径がM以下のものの数
g(n,d) := n頂点の根付き木で、そこからの木の深さの最大値がd以下で、かつ直径がM以下のものの数

g(N,M)が求めたい数である。
g(n,d) = g(n,d-1) + f(n,d)であることから、いったん各f(n,d)が求められればg(N,M)はO(NM)で求められる。
あとはf(n,d)の求め方を考えよう。

d=0の場合は、n=1の場合のみ条件を満たす。
以下dが正の場合を考えると、以下の3通りの和となる。

  • 子が1つの場合、f(n,d) += f(n-1,d-1)
  • 最初の子のsubtreeが深さdを持つ、すなわちこのn頂点の木が深さdを最初のsubtreeで達成する場合、他の子の深さはmin(d,M-d)以下でなければいけないので f(n,d) += f(k, d-1)*f(n-k, min(d,M-d))
  • 最初の子のsubtreeが深さd未満である。すなわちこのn頂点の木が深さdを他のsubtree達成する場合、他の子の深さはどれか1つ深さdを持たなければいけないので f(n,d) += g(k, min(d-1,M-d-1)-1)*f(n-k, d)

後ろ2つは、最初の子頂点のsubtreeの数k=1~(n-2)は総当たりする。
よってf(N,M)は全体でO(N^2*M)で求められる。

int N,M;
ll mo;
ll dp[303][303];
ll dps[303][303];

ll dpdp(int num,int d);
ll dpdps(int num,int d) {
	if(d<0) return 0;
	if(dps[num][d]>=0) return dps[num][d];
	return dps[num][d] = (dpdps(num,d-1) + dpdp(num,d))%mo;
}

ll dpdp(int num,int d) {
	if(num<d) return 0;
	if(dp[num][d]>=0) return dp[num][d];
	if(d==0) {
		return num==1;
	}
	
	ll ret=dpdp(num-1,d-1);
	int k,j;
	for(k=1;k<=num-2;k++) {
		ret += dpdp(k,d-1) * dpdps(num-k,min(d,M-d)) % mo;
		ret += dpdps(k,min(d-2,M-d-1)) * dpdp(num-k,d) % mo;
	}
	return dp[num][d]=ret%mo;
	
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M>>mo;
	MINUS(dp);
	MINUS(dps);
	
	cout<<dpdps(N,M)<<endl;
	
}

まとめ

最初f(n,m)だけからなるO(N^3*M)解を思いついたけど、g(n,m)を導入してO(N^2*M)に落とすのはさほど難しくない。
もう少し時間があれば解けたな…。