概要

\(N\) 個の要素からなる数列をある地点 \(k\) で前後 2 つのチームに分け、それぞれのチームの合計値の差 \(|S_1 - S_2|\) を最小化する問題です。

考察

1. 差の計算式を整理する

チーム A の合計を \(S_1\)、チーム B の合計を \(S_2\)、全メンバーの実力値の総和を \(Total\) とします。 このとき、\(S_2 = Total - S_1\) と表せるため、求めたい差は次のように変形できます。 $\(|S_1 - S_2| = |S_1 - (Total - S_1)| = |2 \times S_1 - Total|\)\( これにより、\)Total\( をあらかじめ計算しておけば、各境界 \)k\( において \)S_1$ の値さえ分かれば差を計算できるようになります。

2. 効率的な計算方法

境界 \(k\) を \(1\) から \(N-1\) まで順番に試すことを考えます。 - 素朴な方法: 各 \(k\) に対して \(S_1\) を \(A_1 + \dots + A_k\) と計算すると、各ステップで最大 \(O(N)\) かかり、全体で \(O(N^2)\) の時間がかかります。\(N = 2 \times 10^5\) のため、これでは制限時間に間に合いません。 - 効率的な方法: 境界 \(k\) を 1 つ右にずらすとき、\(S_1\) に加わるのは新しいメンバーの実力値 \(A_k\) だけです。つまり、前のステップの \(S_1\) に \(A_k\) を足すだけで、次のステップの \(S_1\) が求まります。これなら各ステップ \(O(1)\) で計算でき、全体で \(O(N)\) となり十分に高速です。

アルゴリズム

1. 数列全体の総和 \(Total\) を計算します。
2. チーム A の現在の合計 \(S_1\) を \(0\)、最小の差 \(min\_diff\) を無限大（十分に大きな値）で初期化します。
3. \(k = 1\) から \(N-1\) まで順に以下の操作を行います。
   • \(S_1\) に \(A_k\) を加える。
   • 現在の差 \(|2 \times S_1 - Total|\) を計算する。
   • 計算した差が \(min\_diff\) より小さければ、値を更新する。
   • もし差が \(0\) になった場合は、それ以上小さくなることはないので探索を終了して構いません。
4. 最終的な \(min\_diff\) を出力します。

計算量

• 時間計算量: \(O(N)\)
  • 全体の総和の計算に \(O(N)\)、境界を動かすループに \(O(N)\) かかるため、全体として線形時間で動作します。
• 空間計算量: \(O(N)\)
  • 入力された \(N\) 個の実力値をリストに格納するために \(O(N)\) のメモリを使用します。

実装のポイント

• 高速な入出力: \(N\) が大きいため、Python では sys.stdin.read().split() などを用いて一括で入力を読み込むと実行時間を短縮できます。

• 境界の範囲: 問題文では \(1 \le k < N\) と指定されているため、チーム B が空にならないよう、ループは最後の要素の手前（\(k=N-1\)）までで止める必要があります。

• 絶対値の活用: どちらのチームが大きくても良いため、差を計算する際は必ず abs() 関数を用いて絶対値を取るようにします。

  ソースコード

import sys

def solve():
    # 標準入力から全データを読み込み、空白で分割してリスト化
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # メンバーの人数 N
    n = int(input_data[0])
    # 各メンバーの実力値 A
    a = list(map(int, input_data[1:]))
    
    # 全体の実力値の総和を計算
    total_sum = sum(a)
    
    # チームAの現在の実力値の総和
    current_s1 = 0
    # 最小の差を保持する変数（初期値は無限大）
    min_diff = float('inf')
    
    # 境界 k を 1 から N-1 まで動かす
    # a[i] は 0-indexed なので、i=0 から i=n-2 までループ
    for i in range(n - 1):
        current_s1 += a[i]
        # |S1 - S2| = |S1 - (Total - S1)| = |2 * S1 - Total|
        diff = abs(2 * current_s1 - total_sum)
        
        if diff < min_diff:
            min_diff = diff
        
        # 差が0になった場合はそれ以上小さくならないため終了
        if min_diff == 0:
            break
            
    # 結果を出力
    print(min_diff)

if __name__ == '__main__':
    solve()

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