概要

\(N\) 個の停留所を順番に巡るバスの乗客数の推移をシミュレーションし、最終目的地である停留所 \(N\) に到着して乗客が乗った直後の人数を求める問題です。

考察

この問題のポイントは、各停留所で起きるイベントを順番に、正確に処理することです。

1. 乗車: 現在の人数に \(A_i\) を加える。
2. 下車: 現在の人数から \(B_i\) を引く。ただし、人数が負になることはないので、引いた結果が \(0\) 未満になる場合は \(0\) に補正する。

停留所 \(1\) から \(N-1\) まではこの「乗車」と「下車」の両方の処理を行い、最後の停留所 \(N\) では「乗車」のみを行います。

制約と計算量

停留所の数 \(N\) は最大で \(2 \times 10^5\) です。各停留所での処理は足し算、引き算、および \(0\) との比較（条件分岐）のみであり、これらは定数時間で行えます。したがって、最初から最後まで順番に計算していくシミュレーション手法をとれば、全体の計算量は \(O(N)\) となり、実行時間制限内に十分間に合います。

また、乗客数 \(A_i\) や \(B_i\) は最大 \(10^9\) と大きいですが、合計人数は \(2 \times 10^5 \times 10^9 = 2 \times 10^{14}\) 程度になる可能性があるため、大きな整数を扱える型（Pythonでは標準の整数型）を使用する必要があります。

アルゴリズム

以下の手順でシミュレーションを行います。

1. 現在の乗客数を表す変数 current_passengers を \(0\) で初期化する。
2. \(i = 1, 2, \dots, N-1\) について、以下の処理を繰り返す：
   • current_passengers に \(A_i\) を加える。
   • current_passengers から \(B_i\) を引く。
   • もし current_passengers が \(0\) より小さくなったら、current_passengers を \(0\) にする。
3. 最後に、current_passengers に \(A_N\) を加える。
4. current_passengers の値を出力する。

計算量

• 時間計算量: \(O(N)\)
  • 停留所の数 \(N\) に比例した回数のループ処理を行うためです。
• 空間計算量: \(O(N)\)
  • 入力値をすべてリストとして保持する場合、\(N\) に比例したメモリを使用します。

実装のポイント

• 入力の受け取り: \(N\) が大きいため、Pythonでは sys.stdin.read().split() を使うことで、大量の入力を高速に読み込むことができます。

• 下車の処理: current_passengers -= B のあとに if current_passengers < 0: current_passengers = 0 とするか、current_passengers = max(0, current_passengers - B) と書くことで、「負にならない」という条件を簡潔に実装できます。

• ループの範囲: 最後の停留所 \(N\) だけは下車の処理（\(B_i\)）が存在しないため、ループを \(N-1\) 回で止めるか、条件分岐で \(N\) 番目の処理を分ける必要があります。

  ソースコード

import sys

def solve():
    # 入力をすべて取得
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    N = int(input_data[0])
    current_passengers = 0
    idx = 1
    
    # 停留所 1 から N-1 までの処理
    for _ in range(N - 1):
        A = int(input_data[idx])
        B = int(input_data[idx + 1])
        idx += 2
        
        # 乗車
        current_passengers += A
        # 下車（0人を下回る場合は全員下車）
        current_passengers -= B
        if current_passengers < 0:
            current_passengers = 0
            
    # 停留所 N での乗車
    A_N = int(input_data[idx])
    current_passengers += A_N
    
    # 結果を出力
    print(current_passengers)

if __name__ == "__main__":
    solve()

この解説は gemini-3-flash-thinking によって生成されました。