SRM591 div2 hard(1000) YetAnotherTwoTeamsProblem

問題

あるサッカークラブに属するn人のメンバー全員の能力 s[0], s[1],...,s[n-1] が与えられる.メンバーをA,Bの2チームに分けて練習したい.次の条件を満たす分け方は何通りあるか.

  • 全てのチームメイトは必ずいずれか一方のチームに属する.
  • チームAの強さ > チームBの強さ
    ただしチームの強さは,そのチームに属するメンバーの能力の総和である.
  • チームAに属する任意のメンバーを1人チームBに移すと
    チームAの強さ < チームBの強さ となる
  • 2 <= n <= 50
  • 1 <= s[i] <= 60000

解法

全てのメンバーの能力の総和をS,チームAの強さをta,チームBの強さをtb,チームAでもっとも能力が低いメンバーをmとおくと次の式を満たします.

ta + tb = S
ta > tb
ta - s[m] < tb + s[m]

ここから次の不等式を導けます.

S/2 < ta < s[m] + S/2

これを満たす全てのtaとmの組み合わせについて,場合の数を数え上げます.

実装

コンテスト中は何を思ったかメモ化再帰でのためにdp[51][60001*51]という配列を確保しようとしていました.その後,ループに修正しているうちに時間切れに.

int n;
int sum;
// {s(i), s(i+1),..} から和がTになるような部分集合の数
ll dp[2][60001*51];
ll & dparr(int i, int j){
    return dp[i%2][j];
}

ll solve(const vector<int> & skill){
    ll ans = 0;
    for(int t=0; t<60001*50; t++){
        if(t == skill[n-1] || t == 0)
            dparr(n-1, t) = 1;
        else
            dparr(n-1, t) = 0;
    }
    if(skill[n-1] > sum - skill[n-1]) ans++;
    for(int i=n-2; i>=0; i--){
        for(int t=0; t<60001*50; t++){
            // 漸化式
            if(t - skill[i] >= 0){
                dparr(i, t) = dparr(i+1, t) + dparr(i+1, t-skill[i]);
            } else {
                dparr(i, t) = dparr(i+1, t);
            }
        }
        for (int t1 = sum/2+1; t1 < skill[i] + sum/2.0; ++t1){
            //ans += g(i+1, t1-skill[i], skill);
            ans += dparr(i+1, t1-skill[i]);
        }
    }
    pr(ans);
    return ans;
}

class YetAnotherTwoTeamsProblem {
public:
    long long count(vector<int> skill) {
//        memset(dpg,-1,sizeof(dpg));
        memset(dp,0,sizeof(dp));
        sort(skill.begin(), skill.end());
        n = skill.size();
        sum = accumulate(skill.begin(), skill.end(), 0);
        ll ans = solve(skill);
        return ans;
    }
};