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; } };