概要

1つの窓口に \(N\) 人の来客が順番に訪れるとき、最後の客の対応が終了する時刻を求める問題です。各客の到着時刻と対応にかかる時間が与えられ、窓口が空き、かつ客が到着している最も早い時刻に対応が開始されます。

考察

この問題のポイントは、「次の客の対応がいつ始められるか？」を順番にシミュレーションしていくことです。

ある来客 \(i\) の対応が開始されるためには、以下の2つの条件が両方満たされている必要があります。 1. 窓口が空いている: 前の客（来客 \(i-1\)）の対応が終了している必要があります。 2. 客が到着している: 来客 \(i\) 自身が役所に到着している必要があります。

問題文にある通り、来客 \(i\) の対応開始時刻 \(S_i\) は、前の客の終了時刻 \(S_{i-1} + B_{i-1}\) と、自身の到着時刻 \(A_i\) のうち、遅い方の時刻（\(\max\)）となります。

具体例で考えてみましょう。 - 前の客が時刻 \(10\) に終わり、次の客が時刻 \(12\) に到着した場合：窓口は空いていますが客がいないので、開始は時刻 \(12\) です。 - 前の客が時刻 \(15\) に終わり、次の客が時刻 \(12\) に到着済みの場合：客は待っていますが窓口が埋まっているので、開始は時刻 \(15\) です。

このように、直前の客がいつ終わるかという情報さえ持っておけば、順番に計算していくことができます。

アルゴリズム

1. 現在窓口が空く時刻を保持する変数 current_finish_time を \(0\) で初期化します。
2. \(i = 1\) から \(N\) まで、以下の処理を繰り返します。
   • 来客 \(i\) の到着時刻 \(A_i\) と対応時間 \(B_i\) を受け取る。
   • 対応開始時刻を決定する：start_time = max(current_finish_time, A_i)。
   • 対応終了時刻を計算し、current_finish_time を更新する：current_finish_time = start_time + B_i。
3. 最終的な current_finish_time が答えとなります。

計算量

• 時間計算量: \(O(N)\)
  • \(N\) 人の来客に対して、それぞれ定数時間（\(\max\) と加算）の処理を行うため、来客数に比例した時間で計算が終わります。\(N \leq 2 \times 10^5\) なので、十分に高速です。
• 空間計算量: \(O(N)\) または \(O(1)\)
  • 入力をすべてリスト等に保持する場合は \(O(N)\) ですが、1人ずつ読み込んで処理する場合は \(O(1)\) で済みます。

実装のポイント

• 高速な入出力: Pythonの場合、来客数 \(N\) が \(2 \times 10^5\) と比較的大きいため、input() を繰り返すよりも sys.stdin.read().split() などを用いて一括で入力を取得する方が実行時間を短縮できます。

• 大きな数値の扱い: 終了時刻は \(10^9 + 10^9 \times (2 \times 10^5)\) 程度の非常に大きな値になる可能性がありますが、Pythonは標準で多倍長整数を扱えるため、オーバーフローの心配はありません。

  ソースコード

import sys

def solve():
    # 標準入力からすべてのデータを読み込み、空白文字で分割してイテレータを作成します
    # これにより、大量の入力データに対しても高速に処理を行うことができます
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    it = iter(input_data)
    
    # 来客数 N を取得します
    try:
        N = int(next(it))
    except StopIteration:
        return
    
    # current_finish_time は窓口が次に空く時刻、
    # または直前の来客の対応が終了した時刻を保持します
    current_finish_time = 0
    
    for _ in range(N):
        # 各来客の到着時刻 A と対応にかかる時間 B を取得します
        A = int(next(it))
        B = int(next(it))
        
        # 来客 i の対応開始時刻 S_i は、窓口が空いている時刻と
        # 来客が到着した時刻のうち、遅い方の時刻になります
        # S_i = max(current_finish_time, A)
        if A > current_finish_time:
            current_finish_time = A
        
        # 来客 i の対応終了時刻は S_i + B です
        # これを次の来客のための current_finish_time として更新します
        current_finish_time += B
    
    # 最後の来客の対応が終了した時刻を出力します
    print(current_finish_time)

if __name__ == '__main__':
    solve()

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