概要

\(N\) 人の生徒がバスに乗り込む時刻が与えられたとき、全員が乗り終わる時刻（＝最も遅い到着時刻）を特定し、その \(K\) 分後の時刻を求める問題です。

考察

この問題で最も重要なのは、「最後の生徒がバスに乗り込む時刻」とは何かを考えることです。

生徒 \(i\) は時刻 \(T_i\) に乗り込みます。全員が乗り込んだ状態になるのは、すべての \(T_1, T_2, \dots, T_N\) の中で最も大きい値（最大値）の時刻になったときです。

例えば、生徒の到着時刻が \(10, 50, 30\) で、待ち時間 \(K\) が \(15\) の場合を考えます。 1. 時刻 \(10\) に 1 人目が乗り込む。 2. 時刻 \(30\) に 3 人目が乗り込む。 3. 時刻 \(50\) に 2 人目が乗り込み、これで全員が揃う。 4. その \(15\) 分後である時刻 \(65\) に出発する。

このように、入力された時刻リストの中から最大値を探し、そこに \(K\) を足すだけで答えを導き出すことができます。

アルゴリズム

1. 生徒の人数 \(N\) と待ち時間 \(K\) を入力から受け取る。
2. \(N\) 個の時刻 \(T_1, T_2, \dots, T_N\) をリストとして受け取る。
3. リストの中の最大値 \(T_{max}\) を求める。
4. \(T_{max} + K\) を計算し、出力する。

計算量

• 時間計算量: \(O(N)\)
  • \(N\) 個の要素から最大値を探す処理に \(O(N)\) かかります。\(N \leq 10^5\) なので、十分高速に動作します。
• 空間計算量: \(O(N)\)
  • 入力された \(N\) 個の時刻をリストに保持する場合、\(O(N)\) のメモリを使用します。

実装のポイント

• 大きな入力の処理: \(N\) が最大 \(10^5\) と比較的大きいため、Pythonでは input() を繰り返すよりも sys.stdin.read().split() などを使って一括で読み込む方が実行時間を短縮できる場合があります。

• 最大値の取得: Pythonでは組み込み関数の max() を使うことで、リスト内の最大値を効率よく取得できます。

  ソースコード

import sys

def main():
    # 全ての入力を読み込み、空白文字で分割してリストにする
    input_data = sys.stdin.read().split()
    
    if not input_data:
        return
    
    # 生徒の人数 N と、待ち時間 K を取得
    # N = int(input_data[0]) # N は直接計算には使用しない
    K = int(input_data[1])
    
    # 各生徒の乗り込み時刻 T_i は 2 番目以降の要素
    # それらの中から最大値（最後の生徒の時刻）を探す
    T_max = max(map(int, input_data[2:]))
    
    # 出発時刻は 最後の生徒の時刻 + K
    print(T_max + K)

if __name__ == '__main__':
    main()

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