AtCoder ARC #056 : C - 部門分け

80pt解法をゴリ押しした。
http://arc056.contest.atcoder.jp/tasks/arc056_c

問題

N人の人を幾つかのグループに分ける。
グループ分けのスコアは(グループ数)×Kから、異なるグループに属する2人組(i,j)に対しW[i][j]を減少させた値となる。
最適なグループ分けをしたときの最大スコアを求めよ。

解法

O(3^N)のbitdpで解く。
N人のsubsetをbitmaskであらわしたmaskに対し、mask = submask1 ^ submask2となるような、さらにmaskの部分集合を取る取り方を総当たりしていこう。
愚直にsubmask1を総当たりすると、maskの選び方がO(2^N)、submask1もO(2^N)かかり全体でO(4^N)が、maskの部分bitmapであるようなsubmask1の取り方をうまく取ることでO(3^N)で済ませるテクがある。

submask1とsubmask2に対し、それぞれに属する人の対(i,j)は異なるグループに属するので、対応するW[i][j]を引かなければならない。
愚直に計算するとO(N^2)だが、M[mask]をmaskに属する人の対(i,j)のW[i][j]の総和とすると、上記の値はM[mask]-M[submask1]-M[submask2]で取れる。
前処理でこそO(N^2*2^N)かかるが、O(3^N)かかるmask,submask1の総当たり処理においてO(1)で処理できるのがありがたい。

int N,K;
int W[20][20];
ll dp[1<<20];
ll msum[1<<18];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>K;
	FOR(y,N) FOR(x,N) cin>>W[y][x];
	FOR(i,1<<N) FOR(y,N) FOR(x,y) if((i&(1<<x))&&(i&(1<<y))) msum[i]+=W[y][x];
	
	for(int mask=1;mask<1<<N;mask++) {
		dp[mask]=K;
		for(int i=(i-1)&mask; i>0; i=(i-1)&mask) {
			int mask2=mask ^ i;
			dp[mask] = max(dp[mask],dp[i]+dp[mask2]-msum[mask]+msum[i]+msum[mask2]);
		}
	}
	
	cout<<dp[(1<<N)-1]<<endl;
	
	
}

まとめ

O(N*3^N)解法でも定数倍高速化を頑張るとギリギリ通る。
自分は本番2.9sだった。