TopCoder SRM 570 Div1 Medium CentaurCompany
問題
木が与えられる。
この木のそれぞれのノードを、1/2の確率で赤、1/2の確率で白に塗る。
塗り終えた後で、同じ色のノードを全て連結にするために、自由に辺を足す。
ただし、それぞれのノードに新たに追加できる辺は、
1本目は無料で、2本目以降は1ずつのコストがかかる。
このコストの期待値を求めよ。
制約条件
ノードの数≦36
方針
二つの色は対称なので、それぞれの色ごとに連結にするコストは同じ。
したがって、片方の色を連結にするコストを求めればいい。
その色の連結成分の個数をk個、その色のノードの個数をl個とすると、
k - 1本の辺が新たに必要で、これは2(k - 1)個のノードに接続する。
このうちl個は無料なので、2(k - 1) - lのコストがかかる。
連結成分の個数k, ノードの個数をkとしたときの確率は動的計画法により求まる。
dp[i][j][k][l]を、i番目の頂点以下の部分木について、
根の色がjであり、jの色の連結成分がk個あり、jの色のノードがl個あるような状態になる確率とする。
1の色のノードだけを数えるものとすると、
dp[i][0][0][0] = 0.5
dp[i][1][1][1] = 0.5としておいて、
全ての子についてテーブルの更新をすればよい。
ソースコード
int n; vector<vi> e; double dp[40][2][40][40]; void rec(int c, int p){ dp[c][1][1][1] = 0.5; dp[c][0][0][0] = 0.5; rep(i, e[c].size()){ int to = e[c][i]; if(to == p) continue; rec(to, c); double next[2][40][40] = {}; rep(cl, 2) rep(j, 40) rep(k, 40) if(dp[c][cl][j][k]) rep(ccl, 2) rep(jj, 40) rep(kk, 40) if(dp[to][ccl][jj][kk]){ int nj = j + jj - (cl && ccl); next[cl][nj][k + kk] += dp[c][cl][j][k] * dp[to][ccl][jj][kk]; } rep(j, 2) rep(k, 40) rep(l, 40) dp[c][j][k][l] = next[j][k][l]; } } class CentaurCompany { public: double getvalue(vector <int> a, vector <int> b) { n = a.size() + 1; e.clear(); e.resize(n); rep(i, n - 1){ e[--a[i]].pb(--b[i]); e[b[i]].pb(a[i]); } memset(dp, 0, sizeof(dp)); rec(0, 0); double e = 0; rep(i, 40) rep(j, 40){ e += 2 * (dp[0][0][i][j] + dp[0][1][i][j]) * max(0, (i - 1) * 2 - j); } return e; } }