本番終わり際に方針が立ったけど間に合わなかった。
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)に落とすのはさほど難しくない。
もう少し時間があれば解けたな…。