概要

この問題は、与えられた \(N\) 個のお菓子を2つのグループ（高橋君と青木君）に分け、それぞれのグループの美味しさの合計の差を最小化する問題です。これは典型的な「部分和問題」であり、動的計画法（DP）を用いて効率的に解くことができます。

考察

素朴なアプローチ（全探索）とその限界

各お菓子について「高橋君に渡す」「青木君に渡す」の2通りの選択肢があります。お菓子の個数が \(N\) 個あるため、分け方の総数は \(2^N\) 通りになります。 制約を見ると \(N \leq 200\) です。\(2^{200}\) は非常に大きな値（約 \(1.6 \times 10^{60}\)）であり、すべての分け方を愚直に試すと実行時間制限（TLE）になってしまいます。

動的計画法（DP）へのアプローチ

お菓子の分け方を決める際、重要なのは「高橋君が受け取るお菓子の美味しさの合計」です。 お菓子の美味しさの総和を \(S\) とします。高橋君が受け取るお菓子の美味しさの合計を \(T\) とすると、青木君が受け取る合計は自動的に \(S - T\) と決まります。 このとき、二人の合計の差の絶対値は以下のように表せます。 $\(|T - (S - T)| = |2T - S|\)$

したがって、「お菓子の部分集合を選んで、その美味しさの合計を \(T\) にできるか？」という情報が分かれば、作ることが可能なすべての \(T\) について \(|2T - S|\) を計算し、その最小値を求めることができます。 ここで、「それぞれ \(1\) 個以上のお菓子を受け取る」という条件に注意が必要です。高橋君が受け取る合計 \(T\) は、すべての合計 \(S\) のうち、\(0\)（高橋君が0個）と \(S\)（青木君が0個）であってはなりません。よって、探索する \(T\) の範囲は \(1 \leq T \leq S - 1\) となります。

部分和問題の高速化

\(N \leq 200\)、 \(A_i \leq 1000\) より、総和 \(S\) は最大でも \(200 \times 1000 = 200,000\) です。 「合計 \(T\) を作れるか」を判定する配列 dp[T]（真偽値）を用意して更新していくことを考えます。 通常のDPでは \(O(N \times S)\) の計算量がかかります。今回の制約では \(200 \times 200,000 = 4 \times 10^7\) 回の計算となり、通常のループでも十分間に合いますが、C++の std::bitset を用いることで、ビット演算による超高速な遷移が可能になります。

アルゴリズム

1. お菓子の美味しさの総和 \(S\) を計算します。
2. dp 配列（std::bitset）を用意します。dp[x] は美味しさの合計を \(x\) にできるか（1 なら可能、0 なら不可能）を表します。 初期状態は dp[0] = 1、それ以外は 0 とします。
3. 各お菓子 \(A_i\) について、順に dp を更新します。
   • std::bitset を用いる場合、 dp |= (dp << A_i) とすることで、すべての遷移を1つのビット演算で同時に行うことができます。これは「\(A_i\) を選ばない（元の dp）」と「\(A_i\) を選ぶ（dp << A_i）」の論理和（OR）をとることに対応します。
4. \(1 \leq T < S\) の範囲で、 dp[T] が 1 となる \(T\) について \(|2T - S|\) を計算し、その最小値を出力します。

具体例

\(N=3\)、 \(A = [2, 3, 5]\) の場合： - 総和 \(S = 10\)。 - 初期状態: dp の bit 0 が立っている（...0000000001） - \(A_1 = 2\) を処理: dp の bit 0, 2 が立つ（...0000000101） - \(A_2 = 3\) を処理: dp の bit 0, 2, 3, 5 が立つ（...0000101101） - \(A_3 = 5\) を処理: dp の bit 0, 2, 3, 5, 7, 8, 10 が立つ（...10110101101） - \(1 \leq T \leq 9\) の範囲で dp[T] が 1 となる \(T\) は \(2, 3, 5, 7, 8\) です。 - \(T=5\) のとき、差の絶対値は \(|2 \times 5 - 10| = 0\) となり、これが最小値となります。

計算量

• 時間計算量: \(O\left(\frac{N \times S}{w}\right)\) ここで \(w\) はワードサイズ（通常 64）です。\(N \leq 200\), \(S \leq 200,000\) のため、最悪でも約 \(\frac{4 \times 10^7}{64} \approx 6.25 \times 10^5\) 回の単純なビット操作となり、数ミリ秒で高速に動作します。
• 空間計算量: \(O(S)\) サイズ \(S\) の bitset を保持するため、必要なメモリは \(\frac{200,000}{8} \approx 25 \text{ KB}\) 程度と極めて省メモリです。

実装のポイント

• std::bitset の活用: C++の std::bitset を用いることで、配列を用いたDPの遷移 dp[j] = dp[j] | dp[j - A[i]] を dp |= (dp << A[i]) という1行のビットシフトと論理和で簡潔かつ高速に実装できます。

• 端の条件（それぞれ1個以上）: 高橋君と青木君がそれぞれ1個以上受け取る必要があるため、どちらかが0個になるケース（\(T = 0\) または \(T = S\)）を排除してループを \(1 \leq T < S\) で回す必要があります。制約より \(N \ge 2\) なので、必ず1個ずつ分ける方法が存在します。

  ソースコード

#include <iostream>
#include <vector>
#include <numeric>
#include <cmath>
#include <bitset>
#include <algorithm>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N;
    if (!(cin >> N)) return 0;

    vector<int> A(N);
    int S = 0;
    for (int i = 0; i < N; ++i) {
        cin >> A[i];
        S += A[i];
    }

    const int MAX_S = 200005;
    bitset<MAX_S> dp;
    dp[0] = 1;

    for (int a : A) {
        dp |= (dp << a);
    }

    int min_diff = 1e9;
    for (int T = 1; T < S; ++T) {
        if (dp[T]) {
            int diff = abs(2 * T - S);
            if (diff < min_diff) {
                min_diff = diff;
            }
        }
    }

    cout << min_diff << "\n";

    return 0;
}

---

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