概要

\(N\) 人の生徒がそれぞれ時刻 \(T_i\) にバスに乗り込むとき、最後の生徒が乗り込んでから \(K\) 分後の時刻を求める問題です。

考察

この問題で重要なポイントは「最後の生徒がバスに乗り込む時刻」を特定することです。

• 生徒たちがバスに乗り込む時刻は \(T_1, T_2, \ldots, T_N\) とバラバラです
• 「最後の生徒」とは、最も遅い時刻にバスに乗り込む生徒のことです
• つまり、\(T_1, T_2, \ldots, T_N\) の中で最大の値を見つければよいです

具体例で考えてみましょう

例えば、\(N = 3\), \(K = 5\) で、乗車時刻が \(T = [10, 25, 15]\) の場合：

• 生徒1は時刻 \(10\) に乗車
• 生徒2は時刻 \(25\) に乗車（最も遅い）
• 生徒3は時刻 \(15\) に乗車

最後の生徒（生徒2）が乗り込むのは時刻 \(25\) なので、出発の合図は \(25 + 5 = 30\) の時刻になります。

素朴なアプローチで問題ないか？

この問題は単純に「配列の最大値を求めて \(K\) を足す」だけなので、素朴なアプローチで十分高速に解けます。配列の最大値を求めるのは \(O(N)\) で可能であり、\(N \leq 10^5\) という制約では全く問題ありません。

アルゴリズム

1. 入力から \(N\), \(K\) および乗車時刻のリスト \(T\) を受け取る
2. リスト \(T\) の最大値を求める（これが最後の生徒が乗り込む時刻）
3. 最大値に \(K\) を足した値を出力する

Pythonでは max() 関数を使うことで、リストの最大値を簡単に求めることができます。

計算量

• 時間計算量: \(O(N)\)
  • リストの最大値を求めるために、全要素を1回ずつ確認する必要があります
• 空間計算量: \(O(N)\)
  • 入力のリスト \(T\) を格納するための領域が必要です

実装のポイント

• Pythonの組み込み関数 max() を使えば、1行で最大値を取得できます

• \(T_i\) の最大値が \(10^9\)、\(K\) の最大値が \(10^4\) なので、答えは最大で約 \(10^9\) になりますが、Pythonでは整数のオーバーフローを気にする必要はありません

• ソートして最大値を求める方法（\(O(N \log N)\)）もありますが、max() を使う方が効率的です（\(O(N)\)）

  ソースコード

N, K = map(int, input().split())
T = list(map(int, input().split()))
print(max(T) + K)

---

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