Topcoder SRM696 参加日記
0完でレート微増だった。Div1のEasyはなぜこんなに難易度が高いのだろう(解けてない人が多すぎる)。
頂点数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; }