概要

バスがN個の停留所を順に巡り、各停留所で乗車と下車が行われるとき、最終停留所での乗車完了後の乗客数を求める問題です。

考察

各停留所での処理を素直にシミュレーションする方法が考えられますが、停留所数Nが最大20万と多いため、効率的な処理が必要です。重要な観察点は、下車処理が「現在の乗客数とB_iの小さい方」を下車させるという点です。つまり、現在の乗客数がB_i未満の場合は全員が下車し、それ以上の場合はB_i人だけが下車します。この性質を利用して、停留所を順番に処理していくことで効率的に計算できます。

アルゴリズム

1. 現在の乗客数を0で初期化
2. 最初のN-1個の停留所について以下を繰り返す：
   • 現在の乗客数にA_iを加算（乗車処理）
   • 現在の乗客数がB_i未満なら0に、そうでなければB_iを減算（下車処理）
3. 最後の停留所でA_Nを加算（乗車のみ）
4. 最終的な乗客数を出力

このアルゴリズムでは、各停留所での処理が定数時間で行えるため、全体としてO(N)時間で計算できます。

計算量

• 時間計算量: \(O(N)\)
• 空間計算量: \(O(N)\)（入力データを保存するため）

実装のポイント

• 入力形式に注意：最後の停留所にはB_iがない

• 現在の乗客数を管理する変数currentを適切に更新

• 下車処理ではmin(current, B_i)の代わりに、条件分岐で効率的に処理

• 整数オーバーフローに注意（Pythonでは問題ない）

  ソースコード

import sys

def main():
    data = sys.stdin.read().split()
    n = int(data[0])
    A = []
    B = []
    index = 1
    for i in range(n-1):
        A.append(int(data[index]))
        B.append(int(data[index+1]))
        index += 2
    A.append(int(data[index]))
    
    current = 0
    for i in range(n-1):
        current += A[i]
        if current < B[i]:
            current = 0
        else:
            current -= B[i]
    
    current += A[-1]
    print(current)

if __name__ == "__main__":
    main()

この解説は deepseekv3 によって生成されました。