TopCoder SRM593: MayTheBestPetWin

\( A(S) = \sum_{i \in S} A[i] \)
\( A(T) = \sum_{i \in T} A[i] \)
\( B(S) = \sum_{i \in S} B[i] \)
\( B(T) = \sum_{i \in T} B[i] \)

とすると、求めるべき答えは、

\( \max(|A(S) - B(T)| , |A(T) - B(S)|) \)

になる。

\( A(S) + A(T) = \sum A (\equiv sumA) \)
\( B(S) + B(T) = \sum B (\equiv sumB) \)

を使って変形すると

\( \max(|A(S) - B(T)| , |A(T) - B(S)|) \)
\( = \max(|A(S) + (B(S) - sumB)| , |(sumA - A(S)) - B(S)|) \)
\( = \max(|(A(S) + B(S)) - sumB| , |sumA - (A(S) + B(S))|) \)

となり、 \( A(S) + B(S) \) に依存した式になる。あとは \(A(S) + B(S)\) の取りうる値を動的計画法で求めて、それぞれについてに値の最大値を求めればよい。

実装にメモ付き探索を使うと時間的にかなり厳しいので、普通のループ処理で実装したほうがいい。

public class MayTheBestPetWin {
    public int calc(int[] A, int[] B) {
        var sumA = A.Sum();
        var sumB = B.Sum();
        bool[] dp = new bool[10000 * 100 + 1];

        int ans = int.MaxValue;

        dp[0] = true;

        for (int i = 0; i < A.Length; i++) {
            int ab = A[i] + B[i];
            for (int j = dp.Length - 1; j >= 0; j--) {
                if (j - ab >= 0) dp[j] |= dp[j - ab];
            }
        }

        for (int i = 0; i < dp.Length; i++) {
            if (dp[i]) ans = Math.Min(ans,
                 Math.Max(Math.Abs(sumA - i), Math.Abs(sumB - i)));
        }

        return ans;
    }
}