CSAcademy Round #10 : F. Expected Tree Degrees

考察できればコードは簡単。
https://csacademy.com/contest/round-10/#task/expected-tree-degrees

問題

初期状態で0番の頂点だけからなるグラフに、1～(N-1)の頂点を順に連結していく。
i番の頂点は、0～(i-1)番のi個の頂点の何れかに等確率で辺を張る。
その時、各頂点の次数の二乗和を求めよ。

解法

次数aの頂点に、新規で頂点を連結すると、連結された頂点の次数は(a+1)、新規頂点の次数は1なので((a+1)^2+1^2) - a^2 = 2a+2 だけ次数の二乗和が増える。
よってi番までの頂点を連結した場合の次数の平均値A[i]と二乗和T[i]を以下の要領でDPで求めていけば良い。

• T[i] = T[i-1] + 2*A[i-1] + 2
• A[i] = (i * A[i-1] + 2) / (i+1)

ll N;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	double ave=0;
	double tot=0;
	for(i=1;i<N;i++) {
		tot += 2*ave+2;
		ave=(i*ave+2)/(i+1);
	}
	_P("%.12lf\n",tot);
	
}

まとめ

これもっと前の方にあればみんな解きそう。