Gperm [SRM 696 : Div1 Easy]

問題

https://community.topcoder.com/stat?c=problem_statement&pm=14360

0～49でラベル付けされた50頂点の無向グラフがある。
このグラフ上で、任意の順番で頂点に色付けをする。
色付けをする度に両端が色付けされている辺の個数がコストとして発生する。
最適に塗った時、このコストの総和の最小値は？

辺の数の最大 20

帰納的考察（torus711さんの解答を見た）

1. まず辺の数が少ないのが使えそう
2. あと連結成分内で解決しそう
3. 頂点数もそんなに多くないからbitDPかな？という印象
4. 辺の数50はbitDPするにはちょっと多い
5. でも連結成分で考えると、辺の数が最大20ってことは、連結成分の各々の頂点数の最大は21
6. これならbitDPできるぞ

7. とりあえず、連結成分取り出しそうなので、Union-Findライブラリ乗っける（kmjpさんのやつ）
8. 戦略として、両端が色付けされている辺がなるべく増えないように頂点を選択して塗ってけば良さそう
9. 各連結成分について、これを計算する -> dpcalc
10. これを全部でまとめて、増加量が小さい順から順番につなげて、和を取っていけば答え

――壁――

11. チャレンジされました
12. 違うbitDPで解けるみたいです

dp[mask] = maskの辺が両端とも塗られている状態にできる最小のコストの総和

13. 工夫として各頂点に対して、それを塗ると塗ることができる頂点をそれぞれ前計算しておく
14. はーなるほどって感じ

実装

int bit_count(int i) {
	i = i - ((i >> 1) & 0x55555555);
	i = (i & 0x33333333) + ((i >> 2) & 0x33333333);
	return (((i + (i >> 4)) & 0x0F0F0F0F) * 0x01010101) >> 24;
}
//-----------------------------------------------------------------
#define INF INT_MAX/2
int dp[1 << 20];
int mask[50];
//-----------------------------------------------------------------
class Gperm {
public:
	int countfee(vector<int> x, vector<int> y) {
		int n = x.size();
		
		rep(i, 0, n) {
			mask[x[i]] |= 1 << i;
			mask[y[i]] |= 1 << i;
		}

		rep(m, 0, 1 << n) dp[m] = INF;
		dp[0] = 0;

		rep(m, 0, 1 << n) rep(i, 0, 50) {
			int mm = m | mask[i];
			int ndp = dp[m] + n - bit_count(m);
			dp[mm] = min(dp[mm], ndp);
		}

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