概要

\(N\) 日間の旅行において、各日の「収入 \(A_i\)」と「支出 \(B_i\)」が与えられたとき、すべての日程の終了時点で所持金が一度も負にならないようにするために必要な、初期所持金 \(X\) の最小値を求める問題です。

考察

1. 各日終了時の所持金を数式で表す

初期所持金を \(X\) 円とします。\(i\) 日目の収支を \(D_i = A_i - B_i\) とすると、\(k\) 日目の処理が終わった直後の所持金 \(S_k\) は次のように表せます。 $\(S_k = X + (D_1 + D_2 + \dots + D_k)\)$

ここで、\((D_1 + D_2 + \dots + D_k)\) は \(1\) 日目から \(k\) 日目までの収支の合計（累積和）です。これを \(C_k\) と置くと、条件はすべての \(k \in \{1, \dots, N\}\) について以下が成り立つことです。 $\(X + C_k \geq 0\)$

2. 条件を \(X\) について整理する

上の不等式を \(X\) について整理すると、次のようになります。 $\(X \geq -C_k\)$

これがすべての \(k\) について成り立つ必要があるため、\(X\) は「\(-C_k\) の最大値」以上である必要があります。 また、問題文より \(X\) は \(0\) 以上の整数であるため、最終的な答えは次のように求まります。 $\(\text{最小の } X = \max(0, \max_{1 \leq k \leq N} (-C_k))\)$

3. 具体例で考える

例えば、収支 \(A_i - B_i\) が順に +2, -5, +1 だった場合を考えます。 - 1日目終了時の累積収支 \(C_1 = +2\) - 2日目終了時の累積収支 \(C_2 = 2 - 5 = -3\) - 3日目終了時の累積収支 \(C_3 = -3 + 1 = -2\)

この場合、\(-C_k\) の値は -2, 3, 2 となり、その最大値は \(3\) です。 初期所持金 \(X=3\) であれば、各日の終了時の所持金は \(5, 0, 1\) となり、一度も負になりません。\(X=2\) だと 2 日目に \(-1\) となってしまうため、最小値は \(3\) です。

アルゴリズム

累積収支の最小値を管理することで、効率的に解くことができます。

1. 初期所持金を除いた現在の累積収支 current_diff を \(0\)、これまでの累積収支の最小値 min_diff を \(0\) と初期化します。
2. \(i = 1\) から \(N\) まで以下を繰り返します。
   • その日の収支 \(D_i = A_i - B_i\) を計算する。
   • current_diff に \(D_i\) を加算する。
   • もし current_diff が min_diff より小さければ、min_diff を更新する。
3. 累積収支の最小値が例えば \(-3\) であれば、それを打ち消すために \(X=3\) が必要です。したがって、\(\max(0, -min\_diff)\) を出力します。

計算量

• 時間計算量: \(O(N)\)
  • \(N\) 日間のデータを 1 回ずつ走査するため、入力の大きさに比例した時間で計算が終わります。\(N=10^5\) なので、十分高速です。
• 空間計算量: \(O(N)\) または \(O(1)\)
  • 入力値をすべてリストに保持する場合は \(O(N)\)、逐次読み込む場合は \(O(1)\) です。

実装のポイント

• 大きな値の扱い: \(A_i, B_i\) が最大 \(10^9\) であり、\(N\) が \(10^5\) なので、累積収支は最大 \(10^{14}\) 程度になります。Python では整数の大きさに制限がないためそのまま計算できますが、他の言語（C++など）では 64bit 整数型（long long など）を使用する必要があります。

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

  ソースコード

import sys

def solve():
    # 標準入力からすべてのデータを読み込み、空白で分割してリスト化します
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # イテレータを使用してデータを順番に取得します
    it = iter(input_data)
    N = int(next(it))
    
    # current_diff は、初期所持金 X を除いた i 日目終了時点の累積収支を表します
    current_diff = 0
    # min_diff は、累積収支の最小値を保持します
    min_diff = 0
    
    for _ in range(N):
        A = int(next(it))
        B = int(next(it))
        # i 日目の収支 (A_i - B_i) を累積収支に加算します
        current_diff += (A - B)
        # 累積収支がこれまでの最小値を下回った場合、更新します
        if current_diff < min_diff:
            min_diff = current_diff
            
    # すべての i 日目において X + (i日目までの累積収支) >= 0 である必要があります
    # つまり、X >= -(i日目までの累積収支) がすべての i で成り立つ必要があります
    # したがって、X は 0 以上かつ max(0, -min_diff) 以上である必要があります
    print(max(0, -min_diff))

if __name__ == '__main__':
    solve()

---

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