TopCoder SRM 770 : Div1 Easy Div2 Hard DeleteArrays

用事とかぶって不参加。
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;
	}
	
}

まとめ

似たようなコードの繰り返しでちょっと面倒な問題。
もう少しシンプルに書けないかな。