概要

各停留所で「乗車→（次の停留所へ行く途中で）下車」を順にシミュレーションし、最終停留所 \(N\) の乗車直後の乗客数を求める問題です。

考察

この問題で重要なのは、各停留所での状態（バスに乗っている人数）は「直前の人数」だけで決まり、過去の詳細な履歴は不要だという点です。

停留所 \(i\)（\(1 \le i \le N-1\)）では - まず \(A_i\) 人が乗るので人数は \(+A_i\) - 次に \(B_i\) 人が降りるが、乗客が足りない場合は全員降りる
つまり「人数から \(B_i\) を引いた結果が負になったら \(0\)」でよい

よって更新式は - \(p \leftarrow p + A_i\) - \(p \leftarrow \max(0, p - B_i)\)

素朴に「降りる人を1人ずつ減らす」などをすると、\(B_i\) が最大 \(10^9\) なのでループが回りすぎてTLEになります。しかし実際は一括で引き算し、負なら \(0\) に丸めれば \(O(1)\) で処理できます。

最後の停留所 \(N\) は「乗車のみ」で下車が発生しない点に注意します。

（例）\(p=3\) のとき \(A_i=5, B_i=10\) なら
乗車後 \(p=8\)、下車は最大8人までなので最終的に \(p=0\)
更新式 \(p=\max(0, 8-10)=0\) と一致します。

アルゴリズム

1. 乗客数 \(p=0\) で開始する。
2. \(i=1\) から \(N-1\) まで繰り返す：
   • \(p \leftarrow p + A_i\)
   • \(p \leftarrow \max(0, p - B_i)\)
3. 最後に \(p \leftarrow p + A_N\) を行う（停留所 \(N\) は下車なし）。
4. \(p\) を出力する。

計算量

• 時間計算量: \(O(N)\)（各停留所を1回ずつ処理）
• 空間計算量: \(O(1)\)（入力以外に必要なのは乗客数など定数個）

実装のポイント

• 下車処理は \(\min(p, B_i)\) を引くのと同値なので、p = max(0, p - B_i) と書くと簡潔です。

• \(N\) が最大 \(2 \times 10^5\) なので、Pythonでは sys.stdin.buffer.read() でまとめて高速に入力すると安定します。

• 停留所 \(N\) の入力だけ形式が異なり \(A_N\) のみなので、ループは \(N-1\) 回にして最後に \(A_N\) を加算します。

  ソースコード

import sys

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    n = data[0]
    idx = 1
    passengers = 0

    for _ in range(n - 1):
        a = data[idx]
        b = data[idx + 1]
        idx += 2
        passengers += a
        passengers = max(0, passengers - b)

    passengers += data[idx]
    print(passengers)

if __name__ == "__main__":
    main()

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