概要

\(N\) 人のメンバーを番号の連続する境界で前半・後半の2チームに分けたとき、両チームの実力値の総和の差の絶対値を最小化する問題です。

考察

問題の整理

分割点 \(k\) を \(1\) から \(N-1\) まで試し、それぞれについて

\[|S_1 - S_2| = |(A_1 + \cdots + A_k) - (A_{k+1} + \cdots + A_N)|\]

を計算し、その最小値を求めます。

素朴なアプローチの問題点

各 \(k\) に対して毎回 \(S_1\) と \(S_2\) を先頭から足し直すと、1回の計算に \(O(N)\)、それを \(N-1\) 回繰り返すので全体で \(O(N^2)\) かかります。\(N\) が最大 \(2 \times 10^5\) の場合、約 \(4 \times 10^{10}\) 回の演算となり TLE（時間制限超過） になります。

重要な気づき

全体の総和を \(T = A_1 + A_2 + \cdots + A_N\) とすると、

\[S_2 = T - S_1\]

なので、

\[|S_1 - S_2| = |S_1 - (T - S_1)| = |2 \cdot S_1 - T|\]

と変形できます。つまり、前半の累積和 \(S_1\) さえ分かれば差が計算できるということです。

さらに、\(k\) を \(1\) ずつ増やすとき \(S_1\) は \(A_k\) だけ増えるので、累積和を逐次更新すれば各 \(k\) に対して \(O(1)\) で計算できます。

具体例

\(N = 4\), \(A = [1, 3, 2, 4]\) の場合、\(T = 10\) です。

\(k\)	\(S_1\)	\(S_2\)	\(\|2 \cdot S_1 - T\|\)
1	1	9	\(\|2 - 10\| = 8\)
2	4	6	\(\|8 - 10\| = 2\)
3	6	4	\(\|12 - 10\| = 2\)

最小値は \(2\) です。

アルゴリズム

1. 全体の総和 \(T\) を計算する。
2. 変数 prefix（前半の累積和）を \(0\) で初期化する。
3. \(k = 1, 2, \ldots, N-1\) の順にループし、各ステップで：
   • prefix に \(A_{k}\)（0-indexed では \(A[k-1]\)）を加える。
   • \(|2 \cdot \text{prefix} - T|\) を計算し、今までの最小値を更新する。
4. 最小値を出力する。

計算量

• 時間計算量: \(O(N)\) — 総和の計算に \(O(N)\)、ループで \(O(N)\)
• 空間計算量: \(O(N)\) — 入力配列の格納（累積和配列を別途作らないため追加は \(O(1)\)）

実装のポイント

• prefix を逐次加算することで、累積和配列を明示的に作らなくても前半の合計を管理できます。

• 差の絶対値を abs(2 * prefix - total) という式で計算しています。\(S_2 = T - S_1\) の関係を利用することで引き算を1回に減らし、シンプルに書けます。

• 最小値の初期値には float('inf') を使い、どんな大きな値とも正しく比較できるようにしています。

• \(k\) の範囲は \(1 \le k < N\) であることに注意しましょう。\(k = 0\)（チーム A が空）や \(k = N\)（チーム B が空）は許されません。

  ソースコード

N = int(input())
A = list(map(int, input().split()))
total = sum(A)
prefix = 0
ans = float('inf')
for k in range(1, N):
    prefix += A[k-1]
    diff = abs(2 * prefix - total)
    if diff < ans:
        ans = diff
print(ans)

---

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