概要

配列をどこか1か所で前半と後半に分けたとき、2つの部分和の差 \(|S_1 - S_2|\) を最小にする問題です。
全ての分け方を試しつつ、和をうまく使い回すことで高速に解けます。

考察

分割位置を \(k\) とすると、

• チーム A の和：\(S_1 = A_1 + A_2 + \cdots + A_k\)
• チーム B の和：\(S_2 = A_{k+1} + A_{k+2} + \cdots + A_N\)

となります。

求めたいのは、\(1 \le k < N\) のすべてについて \(|S_1 - S_2|\) を調べたときの最小値です。

素朴な方法

各 \(k\) ごとに

• 前半の和 \(S_1\) を計算
• 後半の和 \(S_2\) を計算

とすると、1つの \(k\) について \(O(N)\) かかります。
これを全ての \(k\) について行うと、全体で \(O(N^2)\) になります。

制約は \(N \le 2 \times 10^5\) なので、\(O(N^2)\) では間に合いません。

---

重要な気づき

全体の和を

\( \text{total} = A_1 + A_2 + \cdots + A_N \)

として先に求めておけば、前半の和 \(S_1\) が分かれば後半の和 \(S_2\) は

\( S_2 = \text{total} - S_1 \)

で一瞬で求められます。

つまり、分割位置を左から右へ1つずつ動かしながら、

• \(S_1\) に次の要素を足す
• \(S_2 = \text{total} - S_1\) を求める
• 差の最小値を更新する

とすればよいです。

---

具体例

例えば \(A = [1, 3, 2, 4]\) のとき、全体の和は

\( \text{total} = 1+3+2+4 = 10 \)

です。

分割位置を順に見ていくと：

• \(k=1\)
  \(S_1=1\), \(S_2=9\)
  差は \(|1-9|=8\)

• \(k=2\)
  \(S_1=1+3=4\), \(S_2=6\)
  差は \(|4-6|=2\)

• \(k=3\)
  \(S_1=1+3+2=6\), \(S_2=4\)
  差は \(|6-4|=2\)

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

このように、前半の和を少しずつ増やしていくだけで全ての分割を調べられます。

アルゴリズム

1. 配列全体の和 \(\text{total}\) を求める。
2. \(S_1 = 0\) で開始する。
3. 左から \(N-1\) 個目まで順に見て、各回で
   • \(S_1 += A_i\)
   • \(S_2 = \text{total} - S_1\)
   • \(|S_1 - S_2|\) で答えを更新
4. 最後に最小値を出力する。

この方法なら、各要素を1回ずつ見るだけで済みます。

計算量

• 時間計算量: \(O(N)\)
• 空間計算量: \(O(1)\)

実装のポイント

• 分割位置 \(k\) は \(1 \le k < N\) なので、ループは n - 1 個目まで見れば十分です。

• Python では整数が大きくなっても自動で扱えるので、\(A_i \le 10^9\) のような大きい値でも問題ありません。

• コードでは s1 を前半の和、total - s1 を後半の和として管理しています。これにより、後半の和を毎回計算し直す必要がありません。

  ソースコード

import sys

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    n = data[0]
    a = data[1:]
    
    total = sum(a)
    s1 = 0
    ans = float('inf')
    
    for i in range(n - 1):
        s1 += a[i]
        s2 = total - s1
        diff = abs(s1 - s2)
        if diff < ans:
            ans = diff
    
    print(ans)

if __name__ == "__main__":
    main()

---

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