TopCoder SRM 570 Div1 Medium CentaurCompany

Div2は割と簡単だったけど、こちらは結構難しい…
http://community.topcoder.com/stat?c=problem_statement&pm=12428

問題

N点(<=36)からなる木を成しているグラフが与えられる。
各点をそれぞれ1/2の確率で２種類の会社に属させたとする。
異なる会社に属する点同士を結ぶ辺は利用できなくなる。

ここで、同じ会社に属する点同士をすべて連結するため、点同士に辺を加える。
しかし、辺の数自体は制限がないが、各点に追加できる辺は１つまでである。
これで足りない場合、コスト１で点に追加できる辺を１つ増やすことができる。

この条件のもとでコストの期待値を答えよ。

解法

まず、コストを計算する。
会社Aに属す点がVa個、会社Aに属す点同士を結ぶ辺がEa本とする。
Va個を結ぶのに必要な辺は(Va-1)本で、すでにEa本あるので追加する辺は(Va-1-Ea)本。
辺の両端は2*(Va-1-Ea)あって、追加コスト無しで追加できる辺の端はVa個なので結局コストは(Va-2*Ea-2)となる(負ならコスト0)。

後はDPで両会社A・Bに属する点の数・辺毎に組み合わせ数をDFS+DPで計算すればよいが、その場合Va・Vb・Ea・Ebの４要素をN点で計算すると最大O(N^9)かかる。
しかし、最初からコスト値である(Va-2*Ea)と(Vb-2*Eb)の２要素についてDPすればO(N^5)で終わる。

以下は、点0から初めてDFSでDP処理を行う。
同じ会社に属する子の数だけコストが上昇し、親と子が同じ会社なら辺が残るのでコストが2減少する。
最後はコストの和を全体のパターン数2^Nで割れば期待値が求まる。

// index, num cost comp0, cost comp1
ll dp[37][73][73][2];
ll tmp[73][73][2];

class CentaurCompany {
	public:
	vector<int> edge[60];
	int N;
	
	
	void dfs(int cur, int from) {
		vector<int>& e=edge[cur];
		int x,y,z,a,b;
		
		dp[cur][37][36][0]=dp[cur][36][37][1]=1;
		
		FOR(x,e.size()) {
			if(e[x]==from) continue;
			dfs(e[x],cur);
			ZERO(tmp);
			FOR(y,73) FOR(z,73) {
				if(dp[e[x]][y][z][0]==0 && dp[e[x]][y][z][1]==0) continue;
				FOR(a,73) FOR(b,73) {
					if(a+y-36<1 || a+y-36>71 || b+z-36<1 || b+z-36>71) continue;
					if(dp[cur][a][b][0]==0 && dp[cur][a][b][1]==0) continue;
					tmp[a+y-36-2][b+z-36][0] += dp[cur][a][b][0]*dp[e[x]][y][z][0];
					tmp[a+y-36+0][b+z-36][0] += dp[cur][a][b][0]*dp[e[x]][y][z][1];
					tmp[a+y-36][b+z-36+0][1] += dp[cur][a][b][1]*dp[e[x]][y][z][0];
					tmp[a+y-36][b+z-36-2][1] += dp[cur][a][b][1]*dp[e[x]][y][z][1];
				}
			}
			
			memmove(dp[cur],tmp,sizeof(tmp));
		}
		
		return ;
	}
	
	double getvalue(vector <int> a, vector <int> b) {
		int x,y,z,w;
		ll tot=0;
		N=a.size()+1;
		
		FOR(x,N) edge[x].clear();
		
		FOR(x,a.size()) {
			edge[a[x]-1].push_back(b[x]-1);
			edge[b[x]-1].push_back(a[x]-1);
		}
		
		ZERO(dp);
		dfs(0,-1);
		
			tot += (max(0,y-38)+max(0,z-38))*dp[0][y][z][0];
			tot += (max(0,y-38)+max(0,z-38))*dp[0][y][z][1];
		}
		return tot/(double)(1LL<<N);
		
	}

};

まとめ

ちょうどProblem - 294E - Codeforcesが木構造をDFS+DPで処理する問題だったので、おかげですんなり理解できた。