概要

バスの到着時刻が昇順で与えられるので、隣り合うバス同士の到着間隔をすべて計算し、その最小値と最大値を求める問題です。

考察

この問題で求めたいのは「連続する2本のバスの到着間隔」の最小値と最大値です。

到着時刻が \(T_1 < T_2 < \cdots < T_N\) と昇順に並んでいるので、連続する2本のバスの間隔は次の \(N-1\) 個の値になります：

\[T_2 - T_1, \quad T_3 - T_2, \quad \ldots, \quad T_N - T_{N-1}\]

例えば、\(N = 4\) で到着時刻が 100 300 450 1200 の場合： - \(300 - 100 = 200\)（秒） - \(450 - 300 = 150\)（秒） - \(1200 - 450 = 750\)（秒）

となり、最小値は \(150\)、最大値は \(750\) です。

この問題は素朴に全ての差を計算して最小・最大を求めるだけで十分です。\(N\) が最大 \(2 \times 10^5\) なので、\(N-1\) 個の差分を計算してその中から最小・最大を取る \(O(N)\) のアプローチで余裕を持って間に合います。

アルゴリズム

1. \(N\) 本のバスの到着時刻 \(T_1, T_2, \ldots, T_N\) を読み込む。
2. 隣り合う到着時刻の差（間隔）をすべて計算し、リスト diffs に格納する。
   • diffs[i] = T[i+1] - T[i]（\(i = 0, 1, \ldots, N-2\)）
3. diffs の最小値と最大値を出力する。

計算量

• 時間計算量: \(O(N)\)
  • 差分リストの作成に \(O(N)\)、最小値・最大値の計算にそれぞれ \(O(N)\) で、合計 \(O(N)\)。
• 空間計算量: \(O(N)\)
  • 到着時刻のリストと差分リストの格納に \(O(N)\)。

実装のポイント

• Python のリスト内包表記 [T[i+1] - T[i] for i in range(N-1)] を使うと、差分リストを簡潔に作成できます。

• min() と max() を使えば、リストから最小値・最大値を一発で取得できます。

• 到着時刻は狭義単調増加（すべて異なり昇順）なので、差分は必ず正の値になります。特別な場合分けは不要です。

  ソースコード

N = int(input())
T = list(map(int, input().split()))
diffs = [T[i+1] - T[i] for i in range(N-1)]
print(min(diffs), max(diffs))

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