TopCoder SRM 802 : Div1 Medium BestEvenSplit

なんで半日経ってもPractice開かないんだろう。
https://community.topcoder.com/stat?c=problem_statement&pm=16904&rd=18537

問題

N(偶数)頂点からなる無向グラフが与えられる。
このグラフを、N/2個の頂点からなる2つのグラフに分割したとき、誘導グラフの辺の総和が最大となるものについて、その数を求めよ。

解法

半分全列挙を行おう。
一番重いループの中身を軽量化するよう、事前に前処理などしておくと3秒に収まる。

int E[30];
vector<pair<int,int>> cand[16];
ll ret[2000];

class BestEvenSplit {
	public:
	int count(int N, vector <int> X, vector <int> Y) {
		ZERO(E);
		int x,y,i;
		int mask;
		int M=N/2;
		FOR(i,X.size()) {
			E[X[i]]|=1<<Y[i];
			E[Y[i]]|=1<<X[i];
		}
		ZERO(ret);
		FOR(i,M+1) cand[i].clear();
		
		FOR(mask,1<<M) if((mask&1)==0) {
			int pat=0;
			FOR(i,M) {
				if(mask&(1<<i)) pat+=__builtin_popcount(mask&E[i]);
				else pat+=__builtin_popcount((((1<<M)-1)^mask)&E[i]);
			}
			cand[__builtin_popcount(mask)].push_back({mask,pat});
		}
		FOR(mask,1<<M) {
			int pat=0;
			FOR(i,M) {
				if(mask&(1<<i)) pat+=__builtin_popcount(((mask)<<M)&E[i+M]);
				else pat+=__builtin_popcount(((((1<<M)-1)^mask)<<M)&E[i+M]);
			}
			int v=__builtin_popcount(mask);
			int C[2][16]={};
			FOR(i,M) {
				C[0][i]=2*__builtin_popcount(E[i]&((((1<<M)-1)^mask)<<M));
				C[1][i]=2*__builtin_popcount(E[i]&(mask<<M));
			}
			
			FORR(c,cand[M-v]) {
				int npat=pat+c.second;
				FOR(i,M) npat+=C[(c.first>>i)&1][i];
				ret[npat]++;
				
			}
		}
		
		FOR(i,400) if(ret[i]) cout<<i<<" "<<ret[i]<<endl;
		for(i=1999;i>=0;i--) if(ret[i]) return ret[i];
		return 0;
		
	}
}

まとめ

600ptだったので危険かと思ってたけど、最大ケースも試しやすいしそれほど危険でもなかった。