概要

バスが停留所を順番に巡り、各停留所で乗客の乗車・下車が行われるシミュレーション問題です。最終停留所での乗車完了時点の乗客数を求めます。

考察

この問題は、各停留所で行われる処理をそのまま順番にシミュレーションすれば解くことができます。

各停留所 \(i\) での処理は以下の通りです： 1. \(A_i\) 人が乗車する → passengers += A_i 2. \(i \leq N-1\) の場合、\(\min(\text{現在の乗客数}, B_i)\) 人が下車する

ここで「下車」の処理について考えます。\(\min(\text{現在の乗客数}, B_i)\) 人が下車するということは： - 乗客数 \(\geq B_i\) のとき → \(B_i\) 人が下車し、残りは passengers - B_i - 乗客数 \(< B_i\) のとき → 全員が下車し、残りは \(0\) 人

これは passengers = max(0, passengers - B_i) と一行で書けます。

具体例： \(N = 3\), \(A = [5, 3, 2]\), \(B = [2, 4]\) の場合

答えは \(4\) です。

この問題は各停留所を1回ずつ処理するだけなので、素朴なシミュレーションで十分高速に解けます。特別なアルゴリズムは不要です。

アルゴリズム

1. 乗客数 passengers を \(0\) で初期化する。
2. 停留所 \(1\) から \(N-1\) まで順に以下を繰り返す：
   • \(A_i\) を加算する（乗車）。
   • passengers = max(0, passengers - B_i) とする（下車）。
3. 最後の停留所 \(N\) では \(A_N\) を加算するだけ（下車なし）。
4. passengers を出力する。

計算量

• 時間計算量: \(O(N)\) — 各停留所を1回ずつ処理するため
• 空間計算量: \(O(1)\) — 乗客数を保持する変数のみ使用（入力を都度読み込むため配列不要）

実装のポイント

• 入力形式に注意が必要です。停留所 \(1\) から \(N-1\) までは各行に \(A_i\) と \(B_i\) の2つの値が、最後の停留所 \(N\) の行には \(A_N\) の1つの値のみが与えられます。

• 下車時に乗客数が負にならないよう max(0, passengers - B_i) を使います。単に passengers -= B_i としてしまうと、乗客数が負になる場合があり WA になります。

• \(A_i\) や \(B_i\) が最大 \(10^9\)、\(N\) が最大 \(2 \times 10^5\) なので、乗客数は最大で約 \(2 \times 10^{14}\) 程度になり得ます。Python では整数のオーバーフローを気にする必要はありませんが、C++ などでは long long を使う必要があります。

  ソースコード

N = int(input())
passengers = 0
for i in range(N - 1):
    a, b = map(int, input().split())
    passengers += a
    passengers = max(0, passengers - b)
a = int(input())
passengers += a
print(passengers)

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