概要

\(N\) 人の選手を 2 チームに分け、力の合計が小さい方のチームの合計値を最大化する問題です。これは典型的な 分割問題（Partition Problem） に帰着されます。

考察

問題の言い換え

全選手の力の総和を \(S\) とすると、チーム 1 の合計が \(S_1\) ならチーム 2 の合計は \(S_2 = S - S_1\) です。\(\min(S_1, S_2)\) を最大化するには、\(S_1\) をできるだけ \(S/2\) に近づければよいです。

つまり、選手の部分集合を選んで、その力の合計が \(\lfloor S/2 \rfloor\) 以下で最大となる値を求める問題に帰着されます。

素朴なアプローチ

部分和問題は通常、DP配列 dp[j] =「合計 \(j\) が作れるか（true/false）」で解きます。配列サイズは \(S\) で、各要素について更新するので \(O(N \times S)\) です。

\(N \leq 2 \times 10^4\)、\(S \leq 2 \times 10^5\) なので、\(N \times S\) は最大 \(4 \times 10^9\) となり、普通のループでは TLE になる恐れがあります。

ビットセットによる高速化

DP配列の各要素は true/false（1ビット）なので、巨大な整数の各ビットで表現できます。具体的には、整数 mask の第 \(j\) ビットが 1 なら「合計 \(j\) が達成可能」を意味します。

• 初期状態: mask = 1（第 0 ビットだけ 1 → 合計 0 は達成可能）
• 選手の力 \(a\) を加えるとき: mask |= (mask << a)

mask << a は「今までに作れた全ての合計値に \(a\) を足した集合」に対応します。OR を取ることで「\(a\) を使わない場合」と「\(a\) を使う場合」の両方を保持します。

例: \(A = [3, 5, 2]\)、\(S = 10\)、\(\lfloor S/2 \rfloor = 5\)

ステップ	mask（2進数、右が第0ビット）	達成可能な合計
初期	...0001	{0}
\(a=3\) 処理後	...1001	{0, 3}
\(a=5\) 処理後	...100101001	{0, 3, 5, 8}
\(a=2\) 処理後	...10100110101	{0, 2, 3, 5, 7, 8, 10}

\(\leq 5\) で最大の達成可能な値は 5 → 答えは \(5\)。

アルゴリズム

1. 全選手の力の総和 \(S\) を求め、\(\text{target} = \lfloor S/2 \rfloor\) とする。
2. ビットセット（Python の巨大整数）を使い、部分和として達成可能な値をすべて求める。
3. \(\text{target}\) から \(0\) に向かって降順に探索し、達成可能な最大の値を出力する。

計算量

• 時間計算量: \(O(N \times S / w)\)
  • \(w\) はワードサイズ（通常 64）。ビットシフトと OR 演算により、1回の更新が \(O(S/w)\) で行えます。
  • \(N \leq 2 \times 10^4\)、\(S \leq 2 \times 10^5\) なので、実質的に十分高速です。
• 空間計算量: \(O(S / w)\)
  • 巨大整数 1 つ分のビット列を保持します。

実装のポイント

• Python の多倍長整数をビットセットとして活用する点が最大のポイントです。Python は整数のビット長に制限がないため、DP 配列をそのまま 1 つの整数で表現でき、ビットシフト・OR 演算で一括更新できます。

• C++ などでは std::bitset を使って同様の高速化が可能です。

• 最後に mask & (1 << j) で第 \(j\) ビットが立っているかを調べることで、合計 \(j\) が達成可能かどうかを判定します。

  ソースコード

import sys

def main():
    input_data = sys.stdin.read().split()
    N = int(input_data[0])
    A = [int(input_data[i+1]) for i in range(N)]
    
    S = sum(A)
    target = S // 2
    
    # Bitset DP for subset sum
    mask = 1
    for a in A:
        mask |= (mask << a)
    
    # Find largest achievable sum <= target
    for j in range(target, -1, -1):
        if mask & (1 << j):
            print(j)
            return

main()

---

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