概要

配列を「前半（チームA）」と「後半（チームB）」に分ける境界 \(k\) を全て試し、各ときの和の差 \(|S_1-S_2|\) の最小値を求める問題です。
累積的に左側の和を更新しながら見ることで、全体を \(1\) 回の走査で解けます。

考察

重要な観察は、境界 \(k\) を1つ右にずらしたときの変化が小さいことです。

• \(S_1\)（左の和）は、要素を1つ追加するだけ
• \(S_2\)（右の和）は、全体和から \(S_1\) を引けばすぐ求まる

つまり、毎回区間和を最初から計算する必要はありません。

素朴な方法

各 \(k\) について - \(A_1+\cdots+A_k\) - \(A_{k+1}+\cdots+A_N\) を毎回計算すると、1回あたり \(O(N)\)、これを \(N\) 回で合計 \(O(N^2)\)。
\(N \le 2\times10^5\) では間に合いません（TLE）。

改善

最初に全体和 \(total=\sum A_i\) を求め、左和 left を 0 から順に増やします。
境界を \(i\)（0-index）までに置いたとき：

• left += A[i] で \(S_1\)
• \(S_2 = total - left\)
• 差は abs(left - (total - left))

これを \(i=0\) から \(N-2\) まで調べれば、すべての有効な分割（\(1 \le k < N\)）を網羅できます。

アルゴリズム

1. \(N\) と配列 \(A\) を読む
   
2. total = sum(A) を計算
   
3. left = 0, ans = 十分大きい値 で初期化
   
4. i = 0 .. N-2 について繰り返す
   
   • left += A[i]
   • right = total - left
   • diff = abs(left - right)
   • ans = min(ans, diff)
5. ans を出力

例えば \(A=[1,2,3,4]\) のとき： - \(k=1\): \((1)\) と \((2,3,4)\) → 差 \(8\) - \(k=2\): \((1,2)\) と \((3,4)\) → 差 \(4\) - \(k=3\): \((1,2,3)\) と \((4)\) → 差 \(2\)
最小は \(2\)。

計算量

• 時間計算量: \(O(N)\)
• 空間計算量: \(O(1)\)（入力配列を除く補助変数のみ）

実装のポイント

• ループ範囲は range(N - 1) にする（右チームが空にならないようにするため）。

• Python では整数オーバーフローの心配はほぼ不要だが、他言語では long long 相当を使うと安全です（\(A_i\) が大きく総和も大きい）。

• 初期値 ans = 10**30 のように十分大きい値を置けば簡単に最小値更新できます。

  ソースコード

import sys

def main():
    input = sys.stdin.readline
    N = int(input().strip())
    A = list(map(int, input().split()))

    total = sum(A)
    left = 0
    ans = 10**30

    for i in range(N - 1):
        left += A[i]
        right = total - left
        diff = abs(left - right)
        if diff < ans:
            ans = diff

    print(ans)

if __name__ == "__main__":
    main()

---

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