DDPC2016 予選 : D - DDPC特別ビュッフェ

BitDPまでは本番思いついたけど、Aの後Bで折り返すのに気づけなかった。
http://discovery2016-qual.contest.atcoder.jp/tasks/discovery_2016_qual_d

問題

N要素の整数配列Aと、M要素の整数配列Bがある。
任意のAの1要素とBの1要素を入れ替える、という処理をちょうどK回行うことができる。
sum(A)*sum(B)を最小化せよ。

解法

K=1の時、入れ替え方をN*M通り総当たりすればよい。

Kが2以上の時、「ちょうどK回」と言いつつ実はK回以下の入れ替えも可能である。
A[i]とB[j]を入れ替えたいとき、たとえばA[k]とB[j]を入れ替えたのち、A[k]とA[i]を入れ替えれば2回の交換で1要素を入れ替えることができる。
これを繰り返すと、入れ替え回数を無駄に消費できる。

よってAとBのK個以下のいくつかの要素を入れ替え、sum(A)*sum(B)を最大化することを考えよう。
入れ替え回数は最大でもmin(N,M,K)なので問題の制限より55以下である。

まず、bitdpの要領で以下の値を埋めよう。
dp[i][x] := Aの先頭i要素のうちj個の要素を選んで和をxとできるなら、j bit目の値が1になる。
これはdp[i+1][x+A[i]] |= dp[i][x]<<2 で更新するDPで行うことができる。
このDPはO(N^2*max(A))だが、処理の内容が軽いので何とか間に合う。
なお、K個を超える要素は選択できないので、(K+1)桁目以上のbitは消すようにする。

次に同様にBについて同じ処理を行いたいところだが、そうすると後の処理でO(KNM*max(A)*max(B))かかりTLEする。
よって上記Aに対して実行したdp[i][x]を、Bの要素で逆向きに戻して行こう。
(xは負にもなりうる点に注意)

あとはdp[i][x]の最下位bitが1なら、AとBの要素を同じ数だけ選び、差がxだけ変動するような入れ替えが可能なので、(sum(A)-x)*(sum(B)+x)が解の候補となる。

int N,M,K;
int A[60],B[60];
ll AS,BS;
ll ok[22222*110+5];
ll *dp=&ok[22222*55+3];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M>>K;
	FOR(i,N) cin>>A[i], AS+=A[i];
	FOR(i,M) cin>>B[i], BS+=B[i];
	
	ll ma=0;
	if(K==1) {
		FOR(x,N) FOR(y,M) ma=max(ma,(AS-A[x]+B[y])*(BS+A[x]-B[y]));
	}
	else {
		int MA=22222*55;
		K=min(K,55);
		dp[0]=1;
		FOR(i,N) for(x=MA-A[i];x>=0;x--) dp[x+A[i]] |= dp[x]<<1;
		FOR(i,MA+1) dp[i] &= ((1LL<<(K+1))-1);
		FOR(i,M) for(x=-MA+B[i];x<=MA;x++) dp[x-B[i]] |= dp[x]>>1;
		
		for(i=-MA;i<=MA;i++) if(dp[i]&1) ma=max(ma,(AS-i)*(BS+i));
	}
	
	cout<<ma<<endl;
}

まとめ

本番部分点でバグらせまくってしんどかった。