DISCO presents ディスカバリーチャンネル プログラミングコンテスト2016 予選
問題文
A君は $N$ 個の料理を持っていて，それぞれの美味しさは $A_1,A_2,\ldots,A_N$ で与えられる．
B君は $M$ 個の料理を持っていて，それぞれの美味しさは $B_1,B_2,\ldots,B_M$ で与えられる．
ちょうど $K$ 回だけ，A君が持っている料理 $1$ 個とB君が持っている料理 $1$ 個を交換するということを繰り返す．
全体の幸福度は，（A君の持っている料理の美味しさの和）と（B君が持っている料理の美味しさの和）の積で定義される．
最終的な全体の幸福度の最大値を求める問題．
いくつか最初に考察する．
全ての料理の美味しさの総和を $S$ とすると，全体の幸福度を最大化するというのは，A君の持つ料理の美味しさの和を $S/2$ にできるだけ近づけるのと同値．
また，$K$ が $2$ 以上の場合，お互い交換したものをもう $1$ 回交換することで，$2$ 回無駄に交換回数を消費できるし，
（$N,M$ のどちらかが $2$ 以上であれば）渡したいものではないものを $1$ 回渡しておいて，それと本当に渡したかったものを交換するという手順で $1$ 回無駄に交換回数を無駄に消費できる．
よって，A君が最終的に持っている料理として，元々 $A$ が持っていた料理を $N-i$ 個，元々B君が持っていた料理を $i$ 個にできるというのは，
$K=1$ の時は，$i=1$ のみ，
その他の時は，$i=0,1,\ldots,\min(K,N,M)$ の場合，となる．
（$N=M=1$ の場合は，どうせ幸福度は変化しないので，どうやっても答えは合うので気にしなくても大丈夫）
よって，元々A君が持っていた料理から $i$ 個選んで，美味しさの和を $j$ にできるか，ということを計算する．
これは，状態を素直に $(i,j)$ とし，できるかどうかを計算していくような動的計画法によって達成できる．
この動的計画法の時間計算量は $A_\mathrm{max}=\max(A_i), B_\mathrm{max}=\max(B_i)$ として，$O(N^3 A_\mathrm{max} + M^3 B_\mathrm{max})$ になるが，
取りうる値はできるかどうかの $2$ 値なので，ビットに押し込んでビット演算を使えば，例えば，$64$ 個の状態遷移を一度に計算でき，間に合う．
また，それが計算された後は，元々 $A$ が持っていた料理を $N-i$ 個，元々B君が持っていた料理を $i$ 個使う場合に，美味しさの和を $S/2$ に近づける方法を尺取法で探せば良い．
このフェイズの時間計算量は $O(\min(K,N,M) \times (N A_\mathrm{max} + M B_\mathrm{max}))$ となる．
以下の方法では，DPにおいて，美味しさの和を表すのに $64$ 分の $1$ の長さの配列を用意してビット演算したが，使う回数の方をビットで管理したほうが楽だった．
また，動的計画法で，$A_i,B_i$ を別々に $2$ 回行うのではなく，$A_i$ を考慮するときは，$K$ 個まで使える制限下で行い，その後に続けて，$B_i$ を考慮するときに $N$ 個まで使える制限にしてやれば，後の尺取法のフェイズは必要なくなる．
（ただし，DPの計算量は多少増える）
#include<bits/stdc++.h>
using namespace std;
#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)
#define mygc(c) (c)=getchar_unlocked()
#define mypc(c) putchar_unlocked(c)
#define ll long long
#define ull unsigned ll
void reader(int *x){int k,m=0;*x=0;for(;;){mygc(k);if(k=='-'){m=1;break;}if('0'<=k&&k<='9'){*x=k-'0';break;}}for(;;){mygc(k);if(k<'0'||k>'9')break;*x=(*x)*10+k-'0';}if(m)(*x)=-(*x);}
template <class T, class S, class U> void reader(T *x, S *y, U *z){reader(x);reader(y);reader(z);}
void writer(ll x, char c){int s=0,m=0;char f[20];if(x<0)m=1,x=-x;while(x)f[s++]=x%10,x/=10;if(!s)f[s++]=0;if(m)mypc('-');while(s--)mypc(f[s]+'0');mypc(c);}
template<class T> void writerLn(T x){writer(x,'\n');}
template<class S, class T> inline void chmax(S &a, T b){if(a<b)a=b;}
void bitOR(ull a[], ull b[], int stA, int stB, int len){int i,B,E,R,Y,X,G,Z;static ull p[65],q[65];static int f=0;if(!f){f=1;p[0]=0;rep(i,64)p[i+1]=(p[i]<<1)|1ULL;rep(i,65)q[i]=p[64]^p[i];}B=stA/64;E=stA%64;R=(stA+len)/64;Y=(stA+len)%64;X=stA-stB;G=X/64;Z=X%64;if(Z<0)Z+=64,G--;if(stA>stB){if(B==R){if(Z)b[B-G-1]|=(a[B]&p[Y]&q[E])<<(64-Z);b[B-G]|=(a[B]&p[Y]&q[E])>>Z;}else{if(Z)b[B-G-1]|=(a[B]&q[E])<<(64-Z);b[B-G]|=(a[B]&q[E])>>Z;REP(i,B+1,R){if(Z)b[i-G-1]|=a[i]<<(64-Z);b[i-G]|=a[i]>>Z;}if(Z)b[R-G-1]|=(a[R]&p[Y])<<(64-Z);b[R-G]|=(a[R]&p[Y])>>Z;}}else{if(B==R){b[B-G]|=(a[B]&p[Y]&q[E])>>Z;if(Z)b[B-G-1]|=(a[B]&p[Y]&q[E])<<(64-Z);}else{b[R-G]|=(a[R]&p[Y])>>Z;if(Z)b[R-G-1]|=(a[R]&p[Y])<<(64-Z);for(i=R-1;i>B;i--){b[i-G]|=a[i]>>Z;if(Z)b[i-G-1]|=a[i]<<(64-Z);}b[B-G]|=(a[B]&q[E])>>Z;if(Z)b[B-G-1]|=(a[B]&q[E])<<(64-Z);}}}
int N, M, K;
int A[55], B[55];
ull dpA[57][22422], dpB[57][22422];
int arrA[1333333], arrB[1333333], as, bs;
int mnbt[111111];
int main(){
int i, j, k, l, s, z, tar;
int sumA = 0, sumB = 0, blockA, blockB, sum;
ll res = 0;
mnbt[0] = -1;
REP(i,1,1<<16){
rep(j,16) if(i&1<<j) break;
mnbt[i] = j;
}
reader(&N,&M,&K);
rep(i,N) reader(A+i);
rep(i,M) reader(B+i);
sort(A,A+N);
sort(B,B+M);
dpA[0][0] = dpB[0][0] = 1;
rep(i,N){ for(j=i;j>=0;j--) bitOR(dpA[j], dpA[j+1], 0, A[i], sumA+1); sumA += A[i]; }
rep(i,M){ for(j=i;j>=0;j--) bitOR(dpB[j], dpB[j+1], 0, B[i], sumB+1); sumB += B[i]; }
blockA = sumA/64+1;
blockB = sumB/64+1;
sum = sumA + sumB;
tar = sum / 2;
for(k=(K==1?1:0);k<=min(N,K);k++){
l = M - k;
if(l < 0) break;
as = bs = 0;
rep(i,blockA+1) if(dpA[k][i]) rep(j,4){ z=(dpA[k][i]>>(16*j))&65535; while(mnbt[z]>=0) arrA[as++]=i*64+j*16+mnbt[z], z^=(1<<mnbt[z]); }
rep(i,blockB+1) if(dpB[l][i]) rep(j,4){ z=(dpB[l][i]>>(16*j))&65535; while(mnbt[z]>=0) arrB[bs++]=i*64+j*16+mnbt[z], z^=(1<<mnbt[z]); }
j = bs-1;
rep(i,as){
while(j && arrA[i]+arrB[j-1] > tar) j--;
z = arrA[i] + arrB[j];
chmax(res, (ll)z*(sum-z));
if(j==0) continue;
z = arrA[i] + arrB[j-1];
chmax(res, (ll)z*(sum-z));
}
if(sum==(ll)tar*(sum-tar)) break;
}
writerLn(res);
return 0;
}
Current time: 2024年04月25日03時48分46秒
Last modified: 2016年02月05日22時05分40秒 (by laycrs)
Tags: Competitive_Programming AtCoder discovery2016-qual
トップページに戻る
Logged in as: unknown user (not login)