概要

この問題は、選手を 2 チームに分ける問題ですが、本質的には「総和 \(T=\sum A_i\) の半分以下で作れる最大の部分和を求める」問題です。
部分和問題として考え、ビットセット DP を使うと高速に解けます。

考察

まず、チーム 1 の力の合計を \(S_1\)、チーム 2 の力の合計を \(S_2\) とすると、

\(S_1 + S_2 = T\)

です。したがって、どちらか片方の和が決まれば、もう片方も自動的に決まります。

ここで、\(S_1 \leq S_2\) だとすると

\(\min(S_1, S_2)=S_1\)

です。つまり、できるだけ試合を拮抗させるには、

• \(T/2\) を超えない範囲で
• できるだけ大きい部分和

を作ればよいことになります。

言い換えると、

• ある選手たちをチーム 1 に入れる
• その力の合計を \(s\) とする

とき、答えは

\(\max \{ s \mid s \leq \lfloor T/2 \rfloor,\ s \text{ が作れる} \}\)

です。

---

素朴な方法がなぜだめか

1. 全探索

各選手をチーム 1 / チーム 2 のどちらかに入れるので、場合の数は \(2^N\) 通りです。
\(N \leq 2 \times 10^4\) なので、これは当然不可能です。

2. 通常の部分和 DP

よくある DP として、

• \(dp[s] = \text{和 } s \text{ を作れるか}\)

を使う方法があります。
これは遷移が \(O(NT)\) で、ここで \(T=\sum A_i \leq 2 \times 10^5\) です。

制約に代入すると最大で

\(2 \times 10^4 \times 2 \times 10^5 = 4 \times 10^9\)

程度になり、Python では間に合いません。

---

どう高速化するか

ここで、dp[s] を 配列ではなくビット列 で持ちます。

• ビット \(s\) が 1 なら「和 \(s\) を作れる」
• ビット \(s\) が 0 なら「作れない」

とします。

初期状態では、何も選ばない和 \(0\) だけが作れるので

• dp = 1

です。これは 2 進数で ...0001、つまりビット 0 だけが立っている状態です。

選手の力が \(a\) のとき、

• もともと作れる和
• その和に \(a\) を足した和

の両方が新たに作れます。
これはビット演算で

dp |= dp << a

と書けます。

dp << a は「今作れるすべての和に \(a\) を足す」ことに対応しています。
これを全選手について繰り返せば、作れる部分和がすべて分かります。

---

具体例

例えば \(A = [3, 5, 6]\) のときを考えます。

総和は \(T=14\)、半分は \(7\) です。

• 初期: dp = 1
  作れる和: \(\{0\}\)

• \(3\) を使う: dp |= dp << 3
  作れる和: \(\{0,3\}\)

• \(5\) を使う:
  作れる和: \(\{0,3,5,8\}\)

• \(6\) を使う:
  作れる和: \(\{0,3,5,6,8,9,11,14\}\)

このうち \(7\) 以下で最大なのは \(6\) なので、答えは \(6\) です。
実際、もう片方は \(14-6=8\) なので、\(\min(6,8)=6\) が最大になります。

アルゴリズム

1. 入力を読み込み、総和 \(T=\sum A_i\) を求める。
2. dp = 1 とする。
   これは「和 0 が作れる」ことを表す。
3. 各 \(a \in A\) について、
   dp |= dp << a
   を行う。
4. \(half = \lfloor T/2 \rfloor\) を求める。
5. dp のうち、\(0\) から half までのビットだけを取り出す。
6. その中で最も大きい立っているビット位置を答えとして出力する。

コードでは

mask = (1 << (half + 1)) - 1
ans = (dp & mask).bit_length() - 1

としています。

• mask は下位 half+1 ビットだけが 1 の整数
• dp & mask で「\(half\) 以下で作れる和」だけを残す
• bit_length() - 1 で最高位の 1 の位置、つまり最大の作れる和が得られる

という仕組みです。

計算量

\(S=\sum A_i\) とします。

• 時間計算量: \(O\left(N \cdot \frac{S}{w}\right)\) 相当
  
• 空間計算量: \(O(S)\)

ここで \(w\) は 1 ワードのビット数です。
通常の配列 DP の \(O(NS)\) よりかなり高速で、Python でも十分間に合います。

実装のポイント

• dp は「整数 1 個」でビット集合を表しているのがポイントです。

• dp |= dp << a が部分和 DP の遷移そのものになっています。

• 最後に必要なのは \(T/2\) 以下の最大値だけなので、mask で下位ビットだけを抜き出しています。

• bit_length() は「最高位の 1 の位置 + 1」を返すので、最大の和は bit_length() - 1 です。

  ソースコード

import sys

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

    total = sum(A)
    dp = 1  # dp[s] = reachable 여부를 비트 s로表現

    for a in A:
        dp |= dp << a

    half = total // 2
    mask = (1 << (half + 1)) - 1
    ans = (dp & mask).bit_length() - 1
    print(ans)

if __name__ == "__main__":
    main()

---

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