概要

\(N\) 人の選手を 2 つのチームに分け、それぞれのチームの力の合計 \(S_1, S_2\) のうち、小さい方の値を最大化する問題です。 これは、全選手の力の総和を \(T\) としたとき、\(S_1 \leq \lfloor T/2 \rfloor\) を満たす範囲で最大の \(S_1\) を探す「部分和問題」に帰着できます。

考察

1. 部分和問題への帰着

チーム 1 の力の合計を \(S_1\) とすると、チーム 2 の力の合計は \(S_2 = T - S_1\) となります。 \(\min(S_1, S_2)\) を最大化するには、\(S_1\) をできるだけ \(T/2\) に近づければよいことがわかります。 したがって、与えられた \(A_i\) の中からいくつか選んで作れる和のうち、\(T/2\) 以下の最大値を求める問題となります。

2. 素朴な動的計画法（DP）とその限界

通常、部分和問題は以下のような DP で解かれます。 - dp[j] : 合計を \(j\) にすることが可能か（真偽値）

この更新式は dp[j] = dp[j] | dp[j - A_i] となります。 しかし、今回の制約では \(N \leq 2 \times 10^4\)、\(\sum A_i \leq 2 \times 10^5\) です。 単純な DP だと計算量は \(O(N \times \sum A_i) \approx 4 \times 10^9\) となり、制限時間に間に合いません。

3. 高速化の手法

この問題を解くために、2 つの重要な最適化を組み合わせます。

• ビットセット最適化 (Bitset Optimization) DP のテーブルを「非常に大きな整数」のビット列として扱います。 Python では整数型のサイズに制限がないため、巨大な整数をビットセットとして利用できます。 dp |= (dp << A_i) という 1 行の記述で、全状態を一括で更新できるため、計算量が劇的に改善されます（内部的にワードサイズ単位で並列処理されるため、およそ 64 倍程度の高速化が見込めます）。

• 個数制限付き DP のバイナリ分割 (Binary Decomposition) 同じ値の \(A_i\) が複数ある場合、1つずつ処理するのは非効率です。 ある値 \(v\) が \(c\) 個あるとき、それらを \(1, 2, 4, \dots, 2^k, \text{remainder}\) という重みのグループに分割します。 これにより、個数 \(c\) に対して \(\log c\) 回の更新で済むようになり、計算量を大幅に削減できます。

アルゴリズム

1. 全選手の力の総和 \(T\) を計算し、目標値 target = \(T // 2\) を定めます。
2. 各力の値 \(A_i\) の出現回数をカウントします。
3. DP 用の変数 dp を \(1\) （0番目のビットだけが立っている状態）で初期化します。
4. 各力の値 \(v\) とその個数 \(c\) について、バイナリ分割を行います。
   • \(k = 1, 2, 4, \dots\) と増やしながら、dp |= (dp << (v * k)) を行い、個数 \(c\) から \(k\) を引いていきます。
   • 余った個数についても同様に処理します。
   • 常に dp &= mask を行い、target を超える無駄なビットを削ります。
5. 最終的な dp の中で、立っている最も高いビットのインデックス（dp.bit_length() - 1）が答えとなります。

計算量

• 時間計算量: \(O\left(\frac{T \cdot \sum \log(\text{counts})}{w}\right)\) \(T = \sum A_i\)、 \(w\) はマシンのワードサイズ（Python の内部実装に依存）です。 同じ値の選手をまとめることで、実質的な \(N\) が非常に小さくなり、さらにビット演算による高速化が効くため、制限時間内に十分間に合います。
• 空間計算量: \(O(T)\) 巨大な整数（ビットセット）を保持するために必要なメモリ量です。\(T = 2 \times 10^5\) ビットは約 25 KB なので、非常に軽量です。

実装のポイント

• Python の大きな整数: dp |= (dp << shift) は、他の言語の std::bitset と同様の高速化を Python で実現する定石テクニックです。

• マスク処理: dp &= mask を行うことで、target を超えるビットを計算対象から外します。これにより、整数の桁数が肥大化するのを防ぎ、計算速度を維持できます。

• bit_length(): 整数を 2 進数表記したときの長さを返すメソッドで、これを利用して「1 が立っている最大のインデックス」を効率的に取得できます。

  ソースコード

import sys

def solve():
    # 入力を一括で読み込み、空白で分割します。
    data = sys.stdin.read().split()
    if not data:
        return
    
    # Nは選手の人数です。
    N = int(data[0])
    # Aは各選手の力のリストです。
    # 最初の要素Nを除いた、N個の整数を読み込みます。
    A = map(int, data[1:N+1])
    
    # 各力の値の出現回数をカウントし、全選手の力の総和を計算します。
    counts = {}
    total_sum = 0
    for x in A:
        counts[x] = counts.get(x, 0) + 1
        total_sum += x
        
    # 目標値は力の総和の半分（切り捨て）です。
    # min(S1, S2) を最大化することは、S1 <= total_sum // 2 を満たす最大の S1 を見つけることと同じです。
    target = total_sum // 2
    
    # dpはビットセットとして機能する大きな整数です。
    # i番目のビットが1であることは、力の和としてiが作れることを意味します。
    # 初期状態では和0が可能なので、0番目のビットを1（dp = 1）にします。
    dp = 1
    
    # targetまでのビットを保持するためのマスクを作成します。
    # これにより、targetを超える無駄な計算を省き、ビットセットのサイズを抑えます。
    mask = (1 << (target + 1)) - 1
    
    # 同じ力の値が複数ある場合、個数制限付き部分和問題を効率的に解くために
    # バイナリ分割（2進数分割）のテクニックを使用します。
    # これにより、計算量を O(target * N) から O(target * Σ log(counts)) に削減できます。
    for v, c in counts.items():
        # 力の値自体が目標値を超えている場合、その選手をチームに入れると target を超えるため無視します。
        if v > target:
            continue
        
        # 個数 c を 1, 2, 4, ..., 2^k, 残り という形式で分割します。
        k = 1
        while k <= c:
            # v * k の分だけビットを左シフトしてOR演算を行うことで、
            # 新たに作れるようになった和のビットを立てます。
            dp |= (dp << (v * k))
            # targetを超えるビットをマスクで落とします。
            dp &= mask
            c -= k
            k *= 2
        
        # 残りの個数がある場合、それについても同様に処理します。
        if c > 0:
            dp |= (dp << (v * c))
            dp &= mask
            
    # dp.bit_length() - 1 は、dpの中で最も高い位置にある1のビットのインデックスを返します。
    # これが target 以下の範囲で作れる最大の和（S1）になります。
    print(dp.bit_length() - 1)

if __name__ == "__main__":
    solve()

この解説は gemini-3-flash-thinking によって生成されました。