問題

TopCoder Statistics - Problem Statement

解法

tA = sum(A), tB = sum(B) とします。

すると, ある集合 S を決めたとして, maxdiff(S, T) は, max( sum_{i in S} B_i - (tA - sum_{iin S} A_i),  (tB-sum_{iin S}B_i) - sum_{iin S}A_i) となります。これを簡単化すると,
max( sum_{iin S}(A_i+B_i)-tA,  tB-sum_{i in S}(A_i + B_i))となります。

よって,  A_i+B_i のあり得る値がなにかに関する dp を取れば, それらの値のうちどれが最小になるかを確かめるだけで良くなります。

const int MAX = 50*10000*2+1;
bool dp[MAX];

class MayTheBestPetWin {
public:
    int calc(vector <int> A, vector <int> B) {
        int n = A.size();
        int tA = 0, tB = 0;
        for (int el : A) tA += el;
        for (int el : B) tB += el;
        vector<int> plus(n);
        for (int i = 0; i < n; i++) plus[i] = A[i]+B[i];
        memset(dp, false, sizeof(dp));
        dp[0] = true;
        for (int i = 0; i < n; i++) {
            for (int j = MAX-1; j >= 0; j--) {
                if (dp[j]) dp[j+plus[i]] = true;
            }
        }
        int ret = MAX;
        for (int i = 0; i < MAX; i++) if (dp[i]) {
            ret = min(ret, max(i-tA, tB-i));
        }
        return ret;
    }
};