TopCoder SRM 571 Div1 Medium MagicMolecule

先日Div2 Hardの方は力技で解いてしまった問題。
http://community.topcoder.com/stat?c=problem_statement&pm=11705

問題

かなり意訳です。

N点からなる無向グラフが与えられる。
各N個の点にはスコアP[i]が与えられる。

ここからM点以上の点からなるクリークを選び、それらの点の合計スコアを最大化したい。
ただし、3*M >= 2*Nであること。

解法

Nが最大50の時、Mは34となる。50個から34個以上の点を選ぶのはTLEを起こすので無理。
そこで、最初N個全部の点からクリークができてると仮定し、そのうち辺が無い２点A,Bがあったら、そのうちどちらかを外して、残り(N-1)個で同様に繰り返す。
M個以上でクリークが作れたら、合計スコアを求める。

この処理は、最大(N-M)回までA,Bの選択を行うので、O(2^(N-M)*N^2)で処理できる。
そもそもこのクリーク検出は割と有名みたいね。

class MagicMolecule {
	int N,M;
	vector<int> P;
	vector<string> B;
	public:
	int dfs(ll bmask,int left) {
		int ret=0,x,y;
		
		if(left<0) return -1;
		
		FOR(x,N) for(y=x+1;y<N;y++) {
			if((bmask & (1LL<<x)) && (bmask & (1LL<<y)) && B[x][y]=='N') {
				return max(dfs(bmask ^ (1LL<<x),left-1),dfs(bmask ^ (1LL<<y),left-1));
			}
		}
		
		ret = 0;
		FOR(x,N) if(bmask & (1LL<<x)) ret+=P[x];
		return ret;
	}
	
	int maxMagicPower(vector <int> mP, vector <string> mB) {
		int x,y;
		M=N=mP.size();
		P=mP;
		B=mB;
		while(3*(M-1)>=2*N) M--;
		
		return (int)dfs((1LL<<N)-1,N-M);
	}
};

*まとめ

このクリークの作り方は知らなかった。