SRM570 Div1 Medium "CentaurCompany"
問題
http://community.topcoder.com/stat?c=problem_statement&pm=12428
訳
ケンタウルス会社は1~Nと番号付けられたN個のサーバーを保有している。
これらのサーバーは1つのネットワークを形成しており、
そのネットワークは木構造となっている。
言い換えれば、ちょうどN-1本の双方向ケーブルでネットワーク全体がつながるように、
2つのサーバーを結び付けていた。
ケンタウルス会社は、ヒューマン会社とホース会社の2つの新しい会社として、
生まれ変わろうとしていた。
このことにより、2つの会社で、今あるサーバーをランダムにわけることになった。
より具体的には、N個のサーバーのそれぞれを、
フェア(勝率がきっかり5割)なコインゲームによって、
勝ったほうの会社が取得するということである。
全てのサーバーの分割が終わったところで、
2社は、他社のサーバーと繋がっているケーブルを使用せずに、
ネットワークを構築する事にする。
もちろん、同じ会社内のいくつかのサーバー間において、
通信ができなくなってしまうであろう。
しかし、そのようなサーバーは新しいケーブルを使用し、
ネットワークがつながるようにする。
新しいケーブルは自由に追加する事ができる。
しかし、分割後のそれぞれのサーバーには、新しいケーブルを差し込める
空きスロットが1つだけしかない。
サーバーに空きスロットを1つ追加するのにコストが1かかる。
もし希望するのであれば、同じサーバーに複数のスロットを追加する事が出来る。
2社それぞれで、なるべくコストをかけないでネットワークを構築することにした。
あなたはそれぞれN-1個の要素がある、整数の配列a, bが与えられる。
この2つの配列は、元のネットワークでa[i] と b[i]がケーブルで繋がれている事を示す。
2社がネットワークを構築するのにかかる費用の期待値を返せ。
(期待値は、N個のサーバーがとりうる分割方法全てから取得するものである)
制約
2 <= N <= 36
考えた事
ヒューマン会社(またはホース会社)で取得したサーバーにおいて、
サーバー数をn、連結成分数をcとすると、
必要なコストは(c - 1) * 2 - nとなる。
でも2^36通りも試してnとcの数を数える訳にはいかない。
・・・どうすんだ?
DPする
便宜上ヒューマン会社が取得したサーバーの頂点を赤で塗ると表現する。
まず与えられた木を根付き木にする。
それで、例えばある頂点をルートとした部分木で、n=4, c=2となるような、
赤の塗り方の数を求めたいとする。
これは、さらに子要素をルートとした部分木に対して、
再帰的に関数を呼び出せばよい。
上の図の場合だと、子Aと子Bをルートとした部分木で、
以下のような数を出していけばよい。
A B n=4 c=2 の数 * n=0 c=0 の数 + n=4 c=1 の数 * n=0 c=1 の数 + n=4 c=0 の数 * n=0 c=2 の数 + n=3 c=2 の数 * n=1 c=0 の数 + n=3 c=1 の数 * n=1 c=1 の数 + n=3 c=0 の数 * n=1 c=2 の数 + n=2 c=2 の数 * n=2 c=0 の数 + n=2 c=1 の数 * n=2 c=1 の数 + n=2 c=0 の数 * n=2 c=2 の数 + n=1 c=2 の数 * n=3 c=0 の数 + n=1 c=1 の数 * n=3 c=1 の数 + n=1 c=0 の数 * n=3 c=2 の数 + n=0 c=2 の数 * n=4 c=0 の数 + n=0 c=1 の数 * n=4 c=1 の数 + n=0 c=0 の数 * n=4 c=2 の数
n=0 c=2など絶対ありえないものも含まれているが、
とにかくAとBの合計がn=4 c=2となるようなものを出して、計算していく、
また、そのルートを赤で塗るか、白のままにするかのそれぞれで呼び出す必要がある。
上でA, Bの合計がn=4 c=2となるような~と書いたが、
ルート及びその親を、何色に塗ったのかでA, Bに対するn, cが変動する。
親が赤で塗ってあった場合、
ルートを赤に塗ると、nはもちろん1つ増えるが、
親も赤に塗ってあった場合、連結成分としては増えないため、cはそのままで
子要素の合計がn=3 c=2となるものを求めていく。
ルートを白で塗ると、nもcも変わらないため、
子要素の合計がn=4 c=2となるものを求めていく。
親が白で塗ってあった場合、
ルートを赤で塗ると、nが1増えるとともに、
連結成分も増える。
なので子要素の合計がn=3 c=1となるものを求めていく。
ルートを白で塗ると、nもcも変わらないため、
子要素の合計がn=4 c=2となるものを求めていく。
最終的に
全てのn cペアの塗り方の数を出せたら、
それぞれで(c - 2) * 2 - nを使って、コストの総和をだす。
これは、2^N通り塗ってみたときの、片方の会社のコストの合計であるが、
もう一方の会社も同じだけコストがかかるため、2倍にする。
それを2^Nで割れば、1回分割したときの、コストの期待値がでる。
ソースコード
typedef long long ll; ll memo[50][50][50][2]; ll memo2[50][50][50][2]; int N; bool G[50][50]; bool vis[50]; class CentaurCompany { public: // 頂点pの子要素をルートとした部分木において、 // 頂点数・連結成分数の総和がn, cとなるような塗り方の数を返す // // p - ルートの頂点番号 // pColor - ルートを何色に塗ってあるか // n - 頂点数の総和 // c - 連結成分数の総和 // prev - 前にチェックした子要素の頂点番号 ll dfs00( int p, int pColor, int n, int c, int prev ){ // 次の子要素の頂点番号を取得 int child = -1; for( int i = prev + 1; i <= N; i++ ){ if( G[p][i] && !vis[i] ){ child = i; break; } } // もう全ての子要素をチェックした if( child == -1 ){ // 総和がn, cだった! if( n == 0 && c == 0 ){ return 1; }else{ return 0; } } ll& m = memo2[child][n][c][pColor]; if( m != -1 ) return m; ll res = 0; for( int nn = 0; nn <= n; nn++ ){ for( int cc = 0; cc <= nn; cc++ ){ ll me = dfs( child, nn, cc, pColor ); ll after = dfs00( p, pColor, n - nn, c - cc, child ); res += me * after; } } return m = res; } // ある頂点をルートとした部分木において、 // 頂点数がn 連結成分数がcとなるような、塗り方の数を返す // // v - ルートとする頂点 // n - 頂点数 // c - 連結成分数 // pColor - 親の塗られている色 ll dfs( int v, int n, int c, int pColor ){ ll& m = memo[v][n][c][pColor]; if( m != -1 ) return m; if( n == 0 && c == 0 ) return m = 1; vis[v] = true; ll res = 0; // 親が赤 if( pColor == 1 ){ // 自分が赤 if( n > 0 ){ res += dfs00( v, 1, n - 1, c, 0 ); } // 自分が白 res += dfs00( v, 0, n, c, 0 ); } // 親が白 or ルート if( pColor == 0 ){ // 自分が赤 if( n > 0 ){ res += dfs00( v, 1, n - 1, c - 1, 0 ); } // 自分が白 res += dfs00( v, 0, n, c, 0 ); } vis[v] = false; return m = res; } void initGraph( const vector<int>& a, const vector<int>& b ){ N = a.size() + 1; memset( G, false, sizeof(G) ); for( int i = 0; i < a.size(); i++ ){ int u = a[i], v = b[i]; G[u][v] = G[v][u] = true; } } double getvalue(vector <int> a, vector <int> b){ initGraph( a, b ); memset( memo, -1, sizeof(memo) ); memset( memo2, -1, sizeof(memo2) ); memset( vis, false, sizeof(vis) ); // 本当のルートでとりうるn cのペアを試していく ll sum = 0; for( int n = 0; n <= N; n++ ){ for( int c = 0; c <= n; c++ ){ int cost = max( 0, c * 2 - n - 2 ); sum += cost * dfs( 1, n, c, 0 ); } } return 2.0 * sum / (1LL << N); } };