mayoko’s diary

プロコンとかいろいろ。

SRM 593 div2 hard: MayTheBestPetWin

TopCoder

問題

TopCoder Statistics - Problem Statement

解法

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

すると, ある集合 S を決めたとして, maxdiff(S, T) は, max( $\sum_{i \in S} B_i - (tA - \sum_{i\in S} A_i)$ , $(tB-\sum_{i\in S}B_i) - \sum_{i\in S}A_i$ ) となります。これを簡単化すると,
max( $\sum_{i\in 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;
    }
};