yukicoder : No.519 アイドルユニット

また定数倍でゴリ押す…。
http://yukicoder.me/problems/no/519

問題

N人(Nは偶数)のアイドルがいる。
このアイドルを(N/2)組のグループに分けたい。

2人組み合わせたときの人気度が与えられる。
最適にグループを組ませたとき、全グループの人気度の総和の最大値を求めよ。

解法

以下O(N*2^N)のあまりよくないBitDP解法。

以下を考える。f*1を更新していく。

以下のコードは930msで割と重め。

int N;
int mat[24][24];
int ma[1<<24];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(y,N) FOR(x,N) cin>>mat[y][x];
	
	int ret=0;
	for(int mask=0;mask<1<<N;mask++) if((__builtin_popcount(mask)&1)==0) {
		ret=max(ret,ma[mask]);
		FOR(y,N) if((mask&(1<<y))==0) {
			for(x=y+1;x<N;x++) if((mask&(1<<x))==0) {
				int mask2=mask | (1<<y) | (1<<x);
				ma[mask2]=max(ma[mask2],ma[mask]+mat[y][x]);
				ret = max(ret, ma[mask2]);
			}
			break;
		}
	}
	cout<<ret<<endl;
	
}

まとめ

なんで一般マッチングのライブラリなんて持ってるんですかね…。

*1:2^N)-1)が求めたい値である。 f(bitmask) := bitmaskに含まれるアイドル達で構成されるグループの人気度の総和の最大値 アイドル数は偶数であり、かつ人気度は非負なので、全アイドルは必ず誰かと組む。 よってf(bitmask)がわかっているとき、bitmaskに含まれない最小番号のアイドルxとそのアイドルと組む別のアイドルyを総当たりしてf(bitmask | (1<