Topcoder SRM696 参加日記

0完でレート微増だった。Div1のEasyはなぜこんなに難易度が高いのだろう（解けてない人が多すぎる）。

Div1 Easy Gperm

頂点数50、辺の数が1~20の無向グラフがある。初期状態では、いずれの頂点も着色されていない。着色には、両端が着色されている辺の数と等しいコストがかかる。すべての頂点を着色するときの最小コストを算出せよ。

辺の数が20と小さいので、辺の情報でbitDPを行う。
　dp[mask]：辺集合maskを作るための最小コスト
とし、maskはビット1の辺がコストに関係しないもの（両端が着色されていな辺）と定義する。
そして、問題とは逆に、すべてが着色された状態(mask=0、コスト=0)から、色を消すごとにコストを追加していくとうまくいく。

public int countfee(int[] x, int[] y) 
{
    var m = x.Length;

    //各頂点につながるエッジの情報（頂点番号->マスク）
    var v_mask = new int[50];
    for (int i = 0; i < m; i++)
    {
        v_mask[x[i]] |= 1 << i;
        v_mask[y[i]] |= 1 << i;
    }

    //無効なエッジの集合を作るための最小コスト（無効なエッジ：コストに絡まないもの）
    var dp = new int[(1 << m)];
    for (int i = 0; i < (1 << m); i++) dp[i] = Int32.MaxValue / 3;

    //すべてのエッジが有効な状態（全頂点がPaintされている状態）から色を消していく
    dp[0] = 0;
    for (int mask = 0; mask < 1 << m; mask++)
    {
        //それぞれの頂点の色を消してみる
        for (int v = 0; v < 50; v++)
        {
            var mask_erased = mask | v_mask[v];  //色を消した頂点に関連するエッジすべて
            dp[mask_erased] = Math.Min(dp[mask_erased], dp[mask] + m - BitCount(mask));
        }
    }

    return dp[(1 << m) - 1];
}

static int BitCount(int i)
{
    i = i - ((i >> 1) & 0x55555555);
    i = (i & 0x33333333) + ((i >> 2) & 0x33333333);
    return (((i + (i >> 4)) & 0x0F0F0F0F) * 0x01010101) >> 24;
}