概要

\(N\) 個のお菓子を2人に分配する際、それぞれが1個以上受け取る条件の下で、美味しさの合計の差の絶対値を最小化する問題です。部分集合の和に関する動的計画法（DP）で解きます。

考察

問題の言い換え

全体の美味しさの合計を \(S\) とすると、高橋君が受け取るお菓子の美味しさの合計を \(T\) としたとき、青木君の合計は \(S - T\) です。差の絶対値は \(|T - (S - T)| = |2T - S|\) となります。

つまり、\(N\) 個のお菓子から1個以上 \(N-1\) 個以下を選んだ部分集合の和 \(T\) について、\(|2T - S|\) を最小化する問題に帰着できます。

素朴なアプローチ

全ての分け方を列挙すると \(2^N - 2\) 通りあり、\(N \leq 200\) では到底間に合いません。

DPによる解決

部分和問題として、「どの合計値が達成可能か」をDPで管理します。ただし、「1個以上 \(N-1\) 個以下を選ぶ」という制約があるため、各合計値に対して選んだ個数の最小値と最大値を記録します。ある合計値 \(s\) について、最小個数が \(N-1\) 以下かつ最大個数が \(1\) 以上であれば、有効な分け方が存在します。

アルゴリズム

1. 全体の合計 \(S = \sum A_i\) を計算する。
2. DPテーブルとして辞書 dp を用意し、dp[s] = (min_count, max_count) で「合計 \(s\) を達成するのに必要な最小個数と最大個数」を管理する。初期状態は dp[0] = (0, 0)。
3. 各お菓子 \(a\) について、「取る」「取らない」の遷移を行い、DPを更新する：
   • 取らない場合：合計・個数は変化しない
   • 取る場合：合計が \(s + a\) に、個数が \(+1\) になる
   • 同じ合計値に複数の個数が対応する場合、最小値と最大値のみ保持する
4. 全てのお菓子を処理した後、各達成可能な合計値 \(s\) について、個数が \([1, N-1]\) の範囲に入るものがあるか確認し、\(|2s - S|\) の最小値を求める。

具体例

\(N = 3\), \(A = [1, 2, 3]\) の場合、\(S = 6\)。

• 部分和 \(1\)（1個）→ \(|2 \cdot 1 - 6| = 4\)
• 部分和 \(2\)（1個）→ \(|2 \cdot 2 - 6| = 2\)
• 部分和 \(3\)（1個 or 2個）→ \(|2 \cdot 3 - 6| = 0\) ← 最小！
• 部分和 \(4\)（2個）→ \(|2 \cdot 4 - 6| = 2\)
• 部分和 \(5\)（2個）→ \(|2 \cdot 5 - 6| = 4\)

答えは \(0\)（例えば高橋君に \(\{3\}\)、青木君に \(\{1, 2\}\)）。

計算量

• 時間計算量: \(O(N \cdot S)\)（\(S = \sum A_i \leq 200000\)）
  • 各お菓子について、DPテーブルの全エントリを走査・更新する
• 空間計算量: \(O(S)\)
  • DPテーブルのエントリ数は最大 \(S+1\) 個

実装のポイント

• 各合計値に対して選んだ個数の最小値・最大値のみ保持することで、メモリと計算量を抑えている。個数が連続的に達成可能でなくても、min/maxの範囲が \([1, N-1]\) と重なるかの判定で十分。

• DPの更新時に「取る」「取らない」を同時に新しい辞書に書き込むことで、同じお菓子を重複して使うことを防いでいる。

• \(N \geq 2\) であるため、片方が全部取る場合（個数 \(0\) または \(N\)）を除外する必要があるが、min/max による判定で自然に処理できる。

  ソースコード

def solve():
    N = int(input())
    A = list(map(int, input().split()))
    S = sum(A)
    
    # DP: dp[s] = True if subset sum s is achievable
    # We need subsets of size 1 to N-1
    # dp[j] = set of possible subset sizes that achieve sum j, but simpler:
    # Track (sum, count) pairs
    # Since N<=100 and S<=100000, use dp[s] as a set of possible counts, or
    # just track dp[s] = bitmask of possible counts... N<=100 so bitmask too large
    
    # Alternative: dp[s] = (min_count, max_count) of items that can form sum s
    # We need count >= 1 and count <= N-1
    # If any achievable count for sum s is in [1, N-1], it's valid
    
    # Better: dp[s] stores min and max number of items to achieve sum s
    # If min_count <= N-1 and max_count >= 1, then valid
    
    # dp as dict: sum -> (min_items, max_items)
    # Initialize: dp[0] = (0, 0)
    
    dp = {0: (0, 0)}
    
    for a in A:
        new_dp = {}
        for s, (mn, mx) in dp.items():
            # Don't take this item
            if s not in new_dp:
                new_dp[s] = (mn, mx)
            else:
                old_mn, old_mx = new_dp[s]
                new_dp[s] = (min(old_mn, mn), max(old_mx, mx))
            # Take this item
            ns = s + a
            nmn, nmx = mn + 1, mx + 1
            if ns not in new_dp:
                new_dp[ns] = (nmn, nmx)
            else:
                old_mn, old_mx = new_dp[ns]
                new_dp[ns] = (min(old_mn, nmn), max(old_mx, nmx))
        dp = new_dp
    
    ans = float('inf')
    for s, (mn, mx) in dp.items():
        # Check if there's a valid count (between 1 and N-1)
        if mx >= 1 and mn <= N - 1:
            diff = abs(S - 2 * s)
            ans = min(ans, diff)
    
    print(ans)

solve()

---

この解説は claude4.6opus-thinking によって生成されました。