TopCoder SRM 553 Div2 Hard SafeRemoval

SRM553もDPか…。
http://community.topcoder.com/stat?c=problem_statement&pm=11737

問題

整数列Aが与えられる。
この数列から１つずつ要素を削除し、計K個要素を削除する。
その過程で、Aの要素の総和が4で割り切れてはいけない。

上記条件を満たしながらK個要素を削除可能かを答えよ。
可能なら削除後の総和の最大値を求めよ。

解法

まずAの要素を4で割った余りごとに別々の配列に分け、昇順ソートしておく。

各配列について合計K個削除するよう総当たりで削除する数をチェックする。
４つ配列があるのでO(K^3)通り。(３つの配列の削除数を決めれば４つ目は決まるため）

この時、４で割って1,2,3余る数を削除する数に対し、途中経過で数列の総和が４で割れることなく数を削除しきれるかどうかをメモ化再帰で判定する。
４で割って0余る数はいくつ削除しても総和を４で割った余りに影響しないので無視してよい。
これもO(K^3)

上記手順により、各配列の削除数に対し総和が４で割れることなく削除できることを確認したら、各配列から小さい順位に配列要素を削除して総和を求め、最大値を求めればよい。

数列の総和はO(N)で前処理をすればあとはO(1)で求められるので、結局全体でO(K^3)のDPになる。

int dpdp[51][51][51][4];

class SafeRemoval {
	public:
	int okok(int a1,int a2,int a3,int rem) {
		if(a1+a2+a3==0) return 1;
		if(dpdp[a1][a2][a3][rem]!=-1) return dpdp[a1][a2][a3][rem];
		int r=0;
		if(rem!=1 && a1) r |= okok(a1-1,a2,a3,rem-1);
		if(rem!=2 && a2) r |= okok(a1,a2-1,a3,(rem+2)%4);
		if(rem!=3 && a3) r |= okok(a1,a2,a3-1,(rem+1)%4);
		return dpdp[a1][a2][a3][rem]=r;
	}
	
	int removeThem(vector <int> seq, int k) {
		int i,j,a[4];
		vector<int> C[4];
		
		MINUS(dpdp);
		FOR(i,seq.size()) C[seq[i]%4].push_back(seq[i]);
		FOR(i,4) {
			sort(C[i].begin(),C[i].end());
			for(j=C[i].size()-2;j>=0;j--) C[i][j]+=C[i][j+1];
			C[i].push_back(0);
		}
		int ma=-1;
		int S=C[0][0]+C[1][0]+C[2][0]+C[3][0];
		for(a[0]=0;a[0]<=k && a[0]<C[0].size();a[0]++)
			for(a[1]=0;a[1]<=k-a[0] && a[1]<C[1].size();a[1]++)
				for(a[2]=0;a[2]<=k-a[0]-a[1] && a[2]<C[2].size();a[2]++) {
					a[3]=k-a[0]-a[1]-a[2];
					if(a[3]>=C[3].size()) continue;
					if(!okok(a[1],a[2],a[3],S%4)) continue;
					i=a[1]+a[2]*2+a[3]*3;
					if(((S-i)%4)==0) continue;
					ma=max(ma,C[0][a[0]]+C[1][a[1]]+C[2][a[2]]+C[3][a[3]]);
				}
		return ma;
	}
};

まとめ

ここ３問は割とオーソドックスなDPだった。