TopCoder SRM 591 Div2 Hard YetAnotherTwoTeamsProblem

つづいてDiv2 Hard。やっぱりDiv2 HardのほうがDiv1 Mediumより簡単だ。
http://community.topcoder.com/stat?c=problem_statement&pm=12750

問題

整数値配列Sが与えられる。
以下の条件を満たすようにSの要素を2つのグループに分けたい。

• 各要素の和をとると、1つ目のグループのほうが大きい。
• 1つ目のグループのうち任意の要素を2つ目のグループに移すと、要素の和が2つ目のグループの方が大きくなる。

そのような数列の分け方の組み合わせ数を答えよ。

解法

Sの要素をソートし、大きい順にDPでナップサック問題を解いて1つ目のグループに入れる要素の組み合わせ数をカウントする。
S[i]を1つ目のグループに入れる場合、1つ目のグループの和が全体の和の半分を超えて、かつ半分+S[i]未満なら答えの数にカウントする。

要素を大きい順に処理することで、1つ目のグループに入れる要素の最小値がS[i]となるため、S[i+1]以降を2つ目のグループに入れても当然2つ目のグループが半分以上になるので題意を満たす。

要素数をN、要素の値の最大値D=60000とすると、要素の合計が最大NDなので、O(N^2D)程度になる。
最初、大きい順に処理することを思いつかず小さい順にやったらO(N^3D)になってTLEしてしまった。

ll dp[3600000];
set<int> S,S2;

class YetAnotherTwoTeamsProblem {
	public:
	int N;
	long long count(vector <int> skill) {
		int i,j,k,tot=0;
		N=skill.size();
		sort(skill.begin(),skill.end());
		FOR(i,N) tot+=skill[i];
		ll ret = 0;
		
		ZERO(dp);
		dp[0]=1;
		for(i=N-1;i>=0;i--) {
			for(k=max(tot/2+1,skill[i]);2*k <tot+2*skill[i];k++) ret += dp[k-skill[i]];
			for(k=60000*(N-i);k>=0;k--)  dp[k+skill[i]] += dp[k];
		}
		return ret;
	}
};

まとめ

今回のDiv2は実装量が少ないね。