WARush

SRMの結果とか、解けた問題のコードを書いていきます

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となるような、
赤の塗り方の数を求めたいとする。
f:id:Ekaing:20130512215917j:plain

これは、さらに子要素をルートとした部分木に対して、
再帰的に関数を呼び出せばよい。
上の図の場合だと、子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となるものを求めていく。
f:id:Ekaing:20130512215944j:plain


ルートを白で塗ると、nもcも変わらないため、
子要素の合計がn=4 c=2となるものを求めていく。
f:id:Ekaing:20130512215958j:plain


親が白で塗ってあった場合、
ルートを赤で塗ると、nが1増えるとともに、
連結成分も増える。
なので子要素の合計がn=3 c=1となるものを求めていく。
f:id:Ekaing:20130512220329j:plain


ルートを白で塗ると、nもcも変わらないため、
子要素の合計がn=4 c=2となるものを求めていく。
f:id:Ekaing:20130512220056j:plain

最終的に

全ての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);
    }
};