概要

全選手を 2 チームに分ける問題は、「総和の半分にできるだけ近い部分和を作る問題（部分和問題）」に言い換えられます。
ビット集合（bitset）を使った高速な部分和 DP により、制約内で効率よく解けます。

考察

まず、チーム 1 の合計を \(S_1\)、チーム 2 の合計を \(S_2\)、全体の総和を \(T\) とすると
\(S_1 + S_2 = T\) です。

求めたいのは \(\min(S_1, S_2)\) の最大値ですが、これは「2 つの和をできるだけ近づける」ことと同じです。
したがって、\(S_1 \le \lfloor T/2 \rfloor\) の範囲で作れる最大の \(S_1\) を見つければ答えになります。

---

素朴に「各選手をチーム 1 / 2 に入れる」を全探索すると \(2^N\) 通りで、\(N \le 2\times10^4\) では不可能です。

次に典型的な 2 次元 DP（dp[i][s]: i 人目までで和 s を作れるか）を考えると、
計算量は \(O(NT)\) です。ここで \(T=\sum A_i \le 2\times10^5\) なので理論上は大きく、Python では重くなりがちです。

---

そこで bitset DP を使います。
「作れる和の集合」をビット列で持つと、<< a が「全ての和に \(a\) を足す操作」になります。

• dp の bit \(i\) が 1 なら、和 \(i\) が作れる
• 初期状態は和 0 のみ作れるので dp = 1
• 各 a について dp |= dp << a

これで 1 選手分の更新を Python の大きな整数演算でまとめて高速に実行できます。

最後に \(\lfloor T/2 \rfloor\) から 0 へ降順に見て、最初に作れる和 \(s\) が答えです（最大の \(\min(S_1,S_2)\)）。

アルゴリズム

1. 入力を受け取り、総和 \(T=\sum A_i\) を計算する。
2. dp = 1 で初期化する（和 0 が可能）。
3. 各選手の力 a について
   dp |= (dp << a) を行う。
4. half = T // 2 とし、s = half, half-1, ..., 0 を順に調べる。
5. (dp >> s) & 1 == 1 となる最初の s を出力する。

この s が、\(\min(S_1, S_2)\) の最大値。

計算量

• 時間計算量: \(O\!\left(N \cdot \frac{T}{w}\right)\) 相当（\(w\) はワードサイズ、bitset シフト・OR による高速化）
• 空間計算量: \(O(T)\)（到達可能な和を表すビット列）

※ 実装上は Python の多倍長整数で bitset を表現しているため、定数倍が小さく実用的です。

実装のポイント

• dp = 1 は「0 番目のビットだけ立っている」状態を意味します。

• dp |= dp << a は「a を使わない場合」と「a を使う場合」の和集合です。

• 最後は必ず T//2 から下向きに探索することで、条件を満たす最大値を取得できます。

• この問題では答えそのものが \(\min(S_1,S_2)\) なので、見つけた s をそのまま出力してよいです。

  ソースコード

import sys

def main():
    input = sys.stdin.readline
    N = int(input())
    A = [int(input()) for _ in range(N)]

    total = sum(A)
    # bit i of dp is 1 <=> sum i is achievable
    dp = 1
    for a in A:
        dp |= (dp << a)

    half = total // 2
    for s in range(half, -1, -1):
        if (dp >> s) & 1:
            print(s)
            return

if __name__ == "__main__":
    main()

---

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