概要

\(N\) 個のバスの到着時刻が昇順で与えられるので、隣り合う到着時刻の差（到着間隔）をすべて計算し、その中の最小値と最大値を求める問題です。

考察

この問題を解くためのポイントは、「隣り合う要素の差」に着目することです。

バスの到着時刻を \(T_1, T_2, \ldots, T_N\) とすると、連続する \(2\) 本のバスの到着間隔は以下の \(N-1\) 個の値になります。 - \(1\) 本目と \(2\) 本目の間隔： \(T_2 - T_1\) - \(2\) 本目と \(3\) 本目の間隔： \(T_3 - T_2\) - \(\vdots\) - \(N-1\) 本目と \(N\) 本目の間隔： \(T_N - T_{N-1}\)

問題文で「到着時刻は狭義単調増加（ \(T_1 < T_2 < \cdots < T_N\) ）」と保証されているため、これらの間隔は必ず正の整数になります。

\(N\) の最大値は \(2 \times 10^5\) です。すべての間隔を計算するのに必要な操作は \(N-1\) 回なので、計算量は \(N\) に比例します。これは、一般的なプログラミング言語で \(1\) 秒間に処理できる計算量（約 \(10^8\) 回）に対して十分に小さいため、素直にすべての間隔を計算するアプローチで制限時間内に正解できます。

アルゴリズム

1. バスを本数 \(N\) と、各到着時刻 \(T_1, \ldots, T_N\) をリスト（配列）として読み込みます。
2. \(i = 1\) から \(N-1\) まで順番に、隣り合う時刻の差 \(T_{i+1} - T_i\) を計算し、その結果を新しいリストに保存します。
3. 作成した間隔のリストの中から、最小値と最大値を見つけます。
4. 求めた最小値と最大値をスペース区切りで出力します。

計算量

• 時間計算量: \(O(N)\)
  • 入力の読み込み、間隔の計算（ \(N-1\) 回）、最小・最大値の探索のすべてが \(N\) に比例する時間で終了します。
• 空間計算量: \(O(N)\)
  • 到着時刻を格納するリストと、間隔を格納するリストにそれぞれ最大 \(N\) 個の要素を保持します。

実装のポイント

• Pythonでの高速な入力: \(N\) が \(2 \times 10^5\) と比較的大きいため、input() を繰り返すよりも sys.stdin.read().split() を使って一括で読み込むほうが実行時間を短縮できます。

• リスト内包表記: Pythonでは [t[i+1] - t[i] for i in range(n - 1)] のようにリスト内包表記を使うことで、簡潔かつ高速に間隔のリストを作成できます。

• 組み込み関数の活用: 最小値と最大値の取得には、Pythonの組み込み関数である min() と max() を使うのが効率的です。これらは内部的に \(O(N)\) で動作します。

  ソースコード

import sys

def main():
    # 標準入力からすべてのデータを読み込み、空白文字で分割してリストにする
    # Nが最大2*10^5程度であれば、この方法がPythonでは高速です
    data = sys.stdin.read().split()
    if not data:
        return
    
    # 1番目の要素がバスの本数 N
    n = int(data[0])
    
    # 2番目以降の要素が到着時刻 T_1, T_2, ..., T_N
    # これらを整数のリストに変換する
    t = list(map(int, data[1:]))
    
    # 連続する2つのバスの到着間隔をすべて計算し、リストに格納する
    # T_i は狭義単調増加なので、間隔は必ず正の整数になる
    gaps = [t[i+1] - t[i] for i in range(n - 1)]
    
    # 最小の間隔と最大の間隔を求め、スペース区切りで出力する
    # min() と max() は Python の組み込み関数で、リストを1巡して値を求めるため効率的
    print(min(gaps), max(gaps))

if __name__ == '__main__':
    main()

---

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