概要

お菓子を高橋君の集合と青木君の集合に分けるとき、両者の「美味しさ合計」の差の絶対値が最小になる値を求めます。
これは「合計ができるだけ半分に近い部分和を作る」問題（部分和問題）です。

考察

まず、全体の美味しさの合計を \(S=\sum A_i\) とします。
高橋君が受け取る合計を \(x\) とすると、青木君は \(S-x\) です。求めたい差は

\[ |x-(S-x)| = |S-2x| \]

つまり「作れる \(x\)（部分和）の中で \(|S-2x|\) が最小になるもの」を探せばよいです。

素朴な方法が無理な理由

各お菓子を「高橋君に渡す / 青木君に渡す」で考えると分け方は \(2^N\) 通りあり、\(N\le 200\) では全探索は不可能です（\(2^{200}\) は天文学的）。

どう解決するか

「どの合計値 \(x\) が作れるか」を動的計画法（部分和DP）で求めます。
さらに Python では bitset（ビット集合）を整数で表すと、dp |= dp << a のように高速に更新できます。

また条件として「両者は1個以上」なので、 - 高橋君の合計 \(x=0\)（何ももらわない）は禁止 - \(x=S\)（全部もらう）も禁止
よって \(x\) は \(1 \le x \le S-1\) のみを見ます。

アルゴリズム

1. 全体の合計 \(S\) を計算する。
2. bitset DP を行う。
   
   • dp を「和 \(x\) が作れるなら dp の \(x\) ビット目が 1」として持つ。
   • 初期状態は dp = 1（和 0 は作れる）。
   • 各お菓子の美味しさ \(a\) について
     dp |= dp << a
     とする。これは「既に作れる和」に \(a\) を足した和も作れる、をまとめて反映している。
3. \(x=1\) から \(S-1\) まで調べ、作れる \(x\) の中で \(|S-2x|\) の最小値を答える。

（例）\(A=[3,5,8]\) のとき \(S=16\)。作れる \(x\) の中で \(2x\) が 16 に近い（つまり \(x\) が 8 に近い）ものを探せばよい、というイメージです。

計算量

• 時間計算量: \(O\!\left(N \cdot \frac{S}{w}\right)\)（bitset のビット演算。\(w\) は機械語ワード幅相当）
  ※素朴な部分和DPの \(O(NS)\) より実用上かなり速いです。
• 空間計算量: \(O(S)\)（到達可能な和を表すビット列）

実装のポイント

• dp を Python の整数1つで持つと、左シフトと OR で一括更新できて高速です。

• 「両者が1個以上」を満たすため、最終チェックは x を range(1, S)（つまり \(1 \le x \le S-1\)）に限定します。

• 差は abs(S - 2*x) で計算できます（\(|S-2x|\) に対応）。

  ソースコード

import sys

def main():
    it = iter(sys.stdin.read().split())
    N = int(next(it))
    A = [int(next(it)) for _ in range(N)]
    S = sum(A)

    dp = 1  # bitset: dp[x]=1 if sum x is achievable
    for a in A:
        dp |= dp << a

    ans = S
    for x in range(1, S):  # both must be non-empty => exclude 0 and S
        if (dp >> x) & 1:
            diff = abs(S - 2 * x)
            if diff < ans:
                ans = diff

    print(ans)

if __name__ == "__main__":
    main()

この解説は gpt-5.2-high によって生成されました。