概要

\(N\) 日間の旅行において、毎日の収入と支出を順に処理したとき、各日の終了時の所持金が常に \(0\) 以上になるような初期所持金 \(X\) の最小値を求める問題です。

考察

重要な気づき

\(i\) 日目の処理がすべて終わった直後の所持金は、初期所持金 \(X\) と各日の収支の累積和で表せます。

\(i\) 日目終了後の所持金を式で書くと：

\[X + \sum_{k=1}^{i}(A_k - B_k)\]

ここで、\(\sum_{k=1}^{i}(A_k - B_k)\) を 累積和 \(C_i\) とおくと、\(i\) 日目終了後の所持金は \(X + C_i\) です。

条件の整理

すべての \(i\) \((1 \leq i \leq N)\) について、\(X + C_i \geq 0\) が成り立つ必要があります。

これを変形すると：

\[X \geq -C_i \quad (\text{すべての } i \text{ について})\]

つまり、\(X\) は \(-C_i\) の最大値以上でなければなりません。

\[X \geq \max_{1 \leq i \leq N}(-C_i) = -\min_{1 \leq i \leq N}(C_i)\]

さらに \(X \geq 0\) という条件もあるので、答えは：

\[X = \max\left(0, \; -\min_{1 \leq i \leq N}(C_i)\right)\]

具体例

例えば \(N = 3\)、初期所持金 \(X\)、各日の収支が \((A_i - B_i) = (-3, +5, -4)\) の場合：

日目	\(C_i\)（累積和）	終了後の所持金
1	\(-3\)	\(X - 3\)
2	\(+2\)	\(X + 2\)
3	\(-2\)	\(X - 2\)

累積和の最小値は \(C_1 = -3\) なので、\(X \geq -(-3) = 3\) が必要です。よって \(X = 3\) が答えです。

アルゴリズム

1. 各日の収支 \(A_i - B_i\) の累積和を順に計算する。
2. 累積和の最小値 \(\min_{1 \leq i \leq N}(C_i)\) を記録する。
3. 答えは \(\max(0, -\min_{1 \leq i \leq N}(C_i))\) とする。

すべてを1回のループで同時に処理できます。

計算量

• 時間計算量: \(O(N)\) — 各日の収支を1回ずつ処理するだけ
• 空間計算量: \(O(1)\) — 累積和と最小値を保持する変数のみ使用

実装のポイント

• 累積和の最小値 min_cumsum の初期値を \(0\) にしています。これは「累積和が一度も負にならない場合、\(X = 0\) でよい」ことに対応します（\(\max(0, -\min\_cumsum)\) で \(0\) が選ばれる）。

• \(A_i, B_i\) が最大 \(10^9\)、\(N\) が最大 \(10^5\) なので、累積和は最大で \(\pm 10^{14}\) 程度になりえます。Python は整数のオーバーフローがないため、特別な対処は不要です。

  ソースコード

N = int(input())
min_cumsum = 0
cumsum = 0
for _ in range(N):
    a, b = map(int, input().split())
    cumsum += a - b
    if cumsum < min_cumsum:
        min_cumsum = cumsum
X = max(0, -min_cumsum)
print(X)

---

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