概要

各日について必要なのは「その日の終了時点の所持金」が \(0\) 以上かどうかだけなので、各日の変化は \(A_i - B_i\) の差分だけ見れば十分です。
この差分の累積和の最小値を求めれば、必要な初期所持金の最小値が分かります。

考察

旅行開始時の所持金を \(X\) 円とします。

\(i\) 日目までの収支の合計を

\(P_i = \sum_{j=1}^{i}(A_j - B_j)\)

とすると、\(i\) 日目終了時点の所持金は

\(X + P_i\)

です。

この値がすべての \(i\) について \(0\) 以上であればよいので、条件は

\(X + P_i \geq 0 \quad (1 \leq i \leq N)\)

つまり

\(X \geq -P_i \quad (1 \leq i \leq N)\)

です。
したがって、すべての日を満たすために必要な最小の \(X\) は、

\(P_i\) の中で最も小さい値を \(\min P\) とすると

\(X = -\min P\)

になります。

ただし、最初から所持金は \(0\) 以上でなければならないので、累積和が一度も負にならないなら答えは \(0\) です。
これを自然に扱うために、初期状態の累積和 \(0\) も含めて最小値を取ればよく、コードでは min_s = 0 として始めています。

重要な気づき

この問題では、各日の処理途中ではなく、その日の処理がすべて終わった直後だけを見ればよいです。
そのため、収入 \(A_i\) と支出 \(B_i\) を別々に考える必要はなく、1 日ごとの増減 \(A_i - B_i\) だけで十分です。

素朴な方法がよくない理由

例えば、初期所持金 \(X\) をいろいろ試して毎回シミュレーションする方法も考えられます。
しかし、答えを 1 つずつ試すのはもちろん不可能ですし、二分探索を使ったとしてもこの問題ではオーバーです。

実際には必要なのは「累積和がどこまで下がるか」だけなので、1 回の走査で求められます。

具体例

例えば、各日の \(A_i - B_i\) が

\(-3,\ +5,\ -4\)

だったとします。

このとき累積和は

• 1日目後: \(-3\)
• 2日目後: \(2\)
• 3日目後: \(-2\)

最小値は \(-3\) です。
よって、必要な初期所持金の最小値は \(3\) 円です。

実際に \(X=3\) とすると、各日終了後の所持金は

• 1日目後: \(3 + (-3) = 0\)
• 2日目後: \(3 + 2 = 5\)
• 3日目後: \(3 + (-2) = 1\)

となり、すべて \(0\) 以上です。

アルゴリズム

1. 累積収支 s を \(0\) で初期化する。
2. 累積収支の最小値 min_s を \(0\) で初期化する。
3. 各日について、s += A_i - B_i とする。
4. そのたびに min_s = min(min_s, s) を更新する。
5. 最後に -min_s を出力する。

min_s が負なら、その絶対値だけ最初にお金を持っていればよいです。
min_s が \(0\) 以上なら、初期所持金は \(0\) 円で十分です。

計算量

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

実装のポイント

• 初期状態も含めて最小値を考えるため、min_s = 0 から始めます。

• 各日の途中ではなく、その日が終わった後の所持金だけを見ればよいので、A_i - B_i を足していくだけで十分です。

• \(A_i, B_i\) は最大 \(10^9\) ですが、Python なら整数オーバーフローは心配いりません。

  ソースコード

import sys

def main():
    input = sys.stdin.readline
    N = int(input())
    s = 0
    min_s = 0
    for _ in range(N):
        a, b = map(int, input().split())
        s += a - b
        if s < min_s:
            min_s = s
    print(-min_s)

if __name__ == "__main__":
    main()

---

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