用事とかぶって不参加。
https://community.topcoder.com/stat?c=problem_statement&pm=15738
問題
3つの整数列A,B,Cが与えられる。
これらに対し、(数列が残っている限り)以下の作業を任意回数行うことができる。
- A,Bから要素を1つずつ選び、取り除く。その際のコストはX+(取り除いた2つの値)。
- B,Cから要素を1つずつ選び、取り除く。その際のコストはY+(取り除いた2つの値)。
- A,Cから要素を1つずつ選び、取り除く。その際のコストはZ+(取り除いた2つの値)。
残された値の総和を最小化せよ。
また、その際の中でコストを最小化せよ。
解法
コストより残された値の最小化が優先なので、残す値の最小化を考える。
A,B,Cの要素数のうち、1つが過半数なら、その要素を残し残り2つを空にしよう。
例えば|A|>|B|+|C|なら、1つ目と3つ目の手順を繰り返しA以外を空にできる。
また、Aのうち残す要素は小さい順|A|-|B|-|C|個にしよう。
そうするとコストも自動的に確定する。
そうでない場合、総数が偶数だとすると、必ず全要素取り除ける。
また、その場合3つの作業の取れる回数も確定し、コストも確定する。
もし総数が奇数の場合、A,B,Cのうち1個だけ残す場合を考え3通り上記の手順を繰り返せばよい。
ll A[101010]; ll B[101010]; ll C[101010]; ll mo=1000000007; class DeleteArrays { public: vector<long long> doDelete(int a, int b, int c, long long x, long long y, long long z) { int i,j; A[0]=33,A[1]=42; B[0]=13; C[0]=7,C[1]=2; for(i=2;i<a;i++) A[i]=(5*A[i-1]+7*A[i-2])%mo+1; for(i=1;i<b;i++) B[i]=(11*B[i-1])%mo+1; for(i=2;i<c;i++) C[i]=(5*C[i-1]+7*C[i-2])%mo+1; ll S=0; sort(A,A+a); sort(B,B+b); sort(C,C+c); FOR(i,a) S+=A[i]; FOR(i,b) S+=B[i]; FOR(i,c) S+=C[i]; if(a>=b+c) { ll lef=0; FOR(i,a-b-c) lef+=A[i]; return {lef,x*b+z*c+S-lef}; } if(b>=a+c) { ll lef=0; FOR(i,b-a-c) lef+=B[i]; return {lef,x*a+y*c+S-lef}; } if(c>=a+b) { ll lef=0; FOR(i,c-a-b) lef+=C[i]; return {lef,y*b+z*a+S-lef}; } vector<ll> mi={1LL<<60,1LL<<60}; FOR(i,4) { ll co=0; if(i==1) a--, co=A[0]; if(i==2) b--, co=B[0]; if(i==3) c--, co=C[0]; if((a+b+c)%2==0) { int pqr=(a+b+c)/2; int p=pqr-c; int q=pqr-a; int r=pqr-b; vector<ll> tmp={co,p*x+q*y+r*z+S-co}; mi=min(mi,tmp); } if(i==1) a++; if(i==2) b++; if(i==3) c++; } return mi; } }
まとめ
似たようなコードの繰り返しでちょっと面倒な問題。
もう少しシンプルに書けないかな。