概要

各停留所で乗車・下車が行われるバスツアーにおいて、最終的にバスに乗っている乗客の人数を求める問題です。

考察

この問題では、停留所ごとに以下のような操作が行われます： 1. 新たに \(A_i\) 人が乗車する。 2. 次の停留所へ向かう際に、最大 \(B_i\) 人が下車する（ただし、現在の乗客数より多い場合は全員下車）。

したがって、各ステップで「現在の乗客数」を管理しながら、乗車→下車の順に処理していくシミュレーションを行う必要があります。

素朴な方法として、本当に毎回人数を足したり引いたりするシミュレーションを行えば良さそうですが、これは制約が大きい（\(N\) が最大 \(2 \times 10^5\)）ので、全体で \(O(N)\) の処理が必要になります。しかし、乗客数が最大 \(10^9\) オーダーなので、シミュレーション自体は一回あたり定数時間で行えるため、問題なく間に合います。

重要なのは、乗車後に下車処理を行うこと、そして下車人数が現在の乗客数を超えないように \(\min\) を使うことです。

最終的には、停留所 \(N\) で乗車が終わった後の乗客数を出力すればOKです。

アルゴリズム

1. 各停留所の乗車人数 \(A_i\) と下車人数 \(B_i\) を読み込む。
2. 変数 current_passengers を用意して、初期値を \(0\) にする。
3. 各停留所 \(i = 1\) から \(N - 1\) まで以下を繰り返す：
   • \(A_i\) を加算（乗車）
   • \(\min(\text{current\_passengers}, B_i)\) を減算（下車）
4. 最終停留所 \(N\) で \(A_N\) を加算（下車はなし）
5. current_passengers を出力

このように、順番にシミュレーションすることで答えを求めることができます。

例

例えば入力が以下のとき：

3
2 1
3 2
1

• 停留所1：乗車2人 → 下車1人 → 残り1人
• 停留所2：乗車3人 → 合計4人 → 下車2人 → 残り2人
• 停留所3：乗車1人 → 合計3人（これが答え）

計算量

• 時間計算量: \(O(N)\)
• 空間計算量: \(O(N)\) （配列 \(A\) および \(B\) を保持するため）

実装のポイント

• 各停留所の処理は「乗車 → 下車」の順に行うこと。

• 下車人数は現在の乗客数を超えないように \(\min\) を使う。

• 最後の停留所では下車がないことに注意。

  ソースコード

N = int(input())
A = [0] * N
B = [0] * (N - 1)

for i in range(N - 1):
    a, b = map(int, input().split())
    A[i] = a
    B[i] = b

A[N - 1] = int(input())

current_passengers = 0

for i in range(N - 1):
    current_passengers += A[i]
    current_passengers -= min(current_passengers, B[i])

current_passengers += A[N - 1]

print(current_passengers)

---

この解説は qwen3-coder-480b によって生成されました。