Codeforces #428 Div2 E. Mother of Dragons

適当に確信なく解いたら通ってしまった。
http://codeforces.com/contest/839/problem/E

問題

無向グラフが与えられる。
各頂点vに、合計がkとなるよう実数R(v)を割り当てたとする。
頂点u-v間に辺があるとき、R(u)*R(v)がスコアとなる。

最適な実数割り当てを行ったとき、スコアの総和を求めよ。

解法

細かい証明はEditorialに任せるとして、実験してみると最大クリークの頂点数をAをしたとき、それらに均等配分するケースでが解になることがわかる。
あとは最大クリークの頂点数を求めよう。

想定解は半分全列挙のようだ。
自分は下記アルゴリズムを単純に実装したらTLEしたので、適当に枝刈りしたら通ってしまった。
Bron–Kerbosch algorithm - Wikipedia

int N,K;
ll mask[64];
int ma=0;

int bk(ll R,ll P,ll X) {
	static int cma=0;
	int ma=0;
	if(P==0 && X==0) {
		cma=max(cma,__builtin_popcountll(R));
		return __builtin_popcountll(R);
	}
	if(cma>=__builtin_popcountll(R)+__builtin_popcountll(P)) return 0;
	while(P) {
		int i = __builtin_ffsll(P)-1;
		ma = max(ma,bk(R | (1LL<<i), P & mask[i], X & mask[i]));
		P ^= (1LL<<i);
		X |= (1LL<<i);
	}
	return ma;
}


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>K;
	FOR(y,N) {
		FOR(x,N) {
			cin>>i;
			if(i) mask[y] |= 1LL<<x;
		}
	}
	
	x = bk(0,(1LL<<N)-1,0);
	double ret=(x-1.0)/(2*x);
	
	
	_P("%.12lf\n",ret*K*K);
	
}

まとめ

最大クリーク検出のための半分全列挙、過去にも見たことあるのに思い出せないのはよくないな。