TopCoder SRM 696 Div1 Easy Gperm

久々にEasyが全く分からない回だったが、1Chalでレートはキープした。
https://community.topcoder.com/stat?c=problem_statement&pm=14360

問題

N頂点M辺の無向グラフがある。
i番の辺は頂点x[i]とy[i]を結んでいく。
N個の頂点を任意の順で色を塗る。
その際、１個塗る度に辺の両端が色を塗られている辺の数だけスコアが上昇する。

最適な順で頂点を塗るとき、スコアの最小値はいくらか。

解法

１つずつ色を塗るのではなく、逆に色を落としていくことを考えよう。
辺の片方の頂点の色を落とせば、以後はその辺によるスコアは発生しない。

Mが小さいことを利用してbitDPで解く。
dp(mask) := mask中のi bit目が立っている場合、i番目の辺が無効(少なくとも片方の点の色が落ちている)場合の最小スコア。
dp(0)=0から始め、dp*1 = min(dp(mask | F(a)), dp(mask) + (M-bitcount(mask)))
のBitDPで解ける。

class Gperm {
	public:
	int countfee(vector <int> x, vector <int> y) {
		int nex[51]={};
		int i,j,mask;
		int N=50;
		int M=x.size();
		vector<int> dp(1<<M,0x202020);
		
		dp[0]=0;
		FOR(i,N) FOR(j,M) if(x[j]==i || y[j]==i) nex[i] |= 1<<j;
		FOR(mask,1<<M) FOR(i,N) dp[mask | nex[i]] = min(dp[mask | nex[i]], dp[mask] + (M-__builtin_popcount(mask)));
		return dp[(1<<M)-1];
	}
}
||>

*まとめ

*1:2^M)-1)を求めればそれが解。(もう全部の辺がスコアを生じないので、後はどの順で色を落としても問題ない。) i番の辺はx[i]とy[i]のどちらかの色を落とせばスコアを生じなくなる。 頂点aを含む辺のbitmaskをF(a)とすると、各maskに対して色を落とす頂点aを総当たりして dp(mask | F(a