TopCoder SRM 571 Div2 Hard MagicMoleculeEasy

Div1 Mediumと似たようでちょっと違う問題。
http://community.topcoder.com/stat?c=problem_statement&pm=12439

問題

最大50点からなるグラフが与えられる。各点にはスコアが振られている。
この50個中からK個(K<=14)の点を選んだ時、各辺において両端の点の少なくとも片方が選らんだK個の含まれるようにしたい。
そのようなK個の選び方のうち、選んだ点のスコアの合計の最大値を返す。

解法

自分は力技で対応してしまった。
各点において、その点を選んだ場合、隣接点は選んでも選ばなくても良い。
点を選ばない場合、その隣接点はすべて選ばなけれなならない。

上記の条件を勘案して枝刈りしつつ、DFSで処理。
しかしこのままやったら5s以上かかったケースがあったので、整数倍の高速化を実行。
↓例えばこんなところ

• 残り全部をとっても最高点を更新しないならやめる
• １個も辺が無い点は取っても取らなくても良い。K個以下の点で条件を満たせそうな時は、１個も辺が無い点からスコアの高い順に利用する。
• 点集合のスコアの部分和を計算しておき、スコア計算を省力化

class MagicMoleculeEasy {
	public:
	int N,K;
	int matc[60];
	ll mat[60];
	vector<int> P,Q;
	vector<pair<int,int> > order;
	int ret,NQ,NO;
	int tt,tt2;
	int tsum[5][1024];
	
	void check(int left,ll mask) {
		int x,y,cp=0;
		
		if(left>0) cp += Q[left-1];
		
		tt++;
		cp += tsum[0][mask & 1023] + tsum[1][(mask>>10) & 1023] +
		tsum[2][(mask>>20) & 1023] +tsum[3][(mask>>30) & 1023] +tsum[4][(mask>>40) & 1023];
		if(cp<ret) return;
		FOR(x,N) {
			if(mask & (1LL<<x)) continue;
			else if(mat[x] & ~mask) return;
		}
		tt2++;
		ret = max(cp,ret);
	}
	
	void dfs(int ind,ll mask, ll mask2) {
		int x,y,ng=0,cp=0,left;
		int cur;
		
		left = K-__builtin_popcountll(mask);
		if(left<0) return;
		if(ind>=NO) {
			if(left>=0 && left<=NQ) check(left,mask);
			return;
		}
		if(left==0) {
			check(left,mask);
			return;
		}
		
		cur = order[ind].second;
		
		//全部取ってダメならもう追いかけない
		ll tmask=((1LL<<N)-1) & (mask | ~mask2);
		x=min(NQ,left);
		if(x>0) cp = Q[x-1];
		cp = tsum[0][tmask & 1023] + tsum[1][(tmask>>10) & 1023] +
		tsum[2][(tmask>>20) & 1023] +tsum[3][(tmask>>30) & 1023] +tsum[4][(tmask>>40) & 1023];
		if(cp<=ret) return;
		
		if(!(mask&(1LL<<cur))) {
			// これを取らずにokか？
			if((mask2 & mat[cur] & ~mask)==0) dfs(ind+1,mask | mat[cur], mask2 | (1LL<<cur));
			
			mask |= 1LL<<cur;
			left--;
		}
		
		if(left>=0 && left<=NQ) check(left,mask);
		if(left>0) dfs(ind+1, mask, mask2 | (1LL<<cur));
	}
	
	int maxMagicPower(vector <int> mP, vector <string> mB, int k) {
		
		P=mP;
		N=mP.size();
		K=k;
		ret=-1;
		tt=tt2=0;
		int x,y;
		ZERO(mat);
		FOR(x,N) FOR(y,N) if(mB[x][y]=='Y') mat[x]|=1LL<<y;
		FOR(x,N) matc[x]=__builtin_popcountll(mat[x]);
		Q.clear();
		order.clear();
		FOR(x,N) if(mat[x]==0) Q.push_back(P[x]);
		FOR(x,N) if(mat[x]) order.push_back(make_pair(mat[x],x));
		
		sort(Q.begin(),Q.end());
		reverse(Q.begin(),Q.end());
		
		ZERO(tsum);
		FOR(x,N) {
			FOR(y,1024) {
				if(y & (1<<(x%10))) tsum[x/10][y] += P[x];
			}
		}
		
		NQ=Q.size();
		NO=order.size();
		for(x=1;x<=NQ-1;x++) Q[x]+=Q[x-1];
		dfs(0,0,0);
		return ret;
	}
};

まとめ

うーん、定数倍の最適化で無理やり通したけど美しくない。
まだEditorialが出てないのでわからないけど、もう少し計算量を落とす手段があるのかな。
これがわからないとDiv1 Mediumも解けなさそう…。