TopCoder SRM 591: YetAnotherTwoTeamsProblem

最小のスキルの固定して、|skill| 分だけ動的計画法すると O(50 * 50 * 50 * 60000) でTLE。

スキルが高い順に足していくと、最後に足されたスキルが最小のスキルになる。
そのことを利用して、昇順からナップサップの動的計画法をしていく、いざ足し合わせるタイミングで、問題にある条件を満たした場合のみ答えに足していけばよい。計算量は O(50 * 60000) となり十分間に合う。

public class YetAnotherTwoTeamsProblem {
    public long count(int[] skill) {
        skill = skill.OrderByDescending(s => s).ToArray();
        long ans = 0;
        long sum = skill.Sum();

        long[] dp = new long[sum + 1];
        dp[0] = 1;
        foreach (var s in skill) {
            for (int j = dp.Length - 1; j >= 0; j--) {
                if (j - s < 0) continue;
                dp[j] += dp[j - s];
                if (j > sum - j && j - s < sum - j + s) ans += dp[j - s];
            }
        }
        return ans;
    }
}