概要

到着時刻が昇順で与えられた \(N\) 本のバスについて、隣り合う到着時刻の差（到着間隔）をすべて調べ、その最小値と最大値を求めます。

考察

連続する 2 本のバスの到着間隔は、到着時刻列 \(T_1 < T_2 < \cdots < T_N\) に対して
\(T_{i+1} - T_i \ (1 \le i \le N-1)\) の \(N-1\) 個だけです。

ここで重要なのは、「連続する」と明記されている点です。
もし「任意の 2 本の間隔」だとすると全組み合わせを調べる必要があり、\(O(N^2)\) になって \(N \le 2\times 10^5\) では到底間に合いません（約 \(4\times 10^{10}\) 組）。

しかし本問は連続するペアだけなので、必要なのは隣同士の差分を順に計算することだけです。例えば
\(T = [10, 40, 55, 100]\) なら間隔は \([30, 15, 45]\) で、最小 \(15\)、最大 \(45\) が答えになります。

アルゴリズム

1. 入力で与えられた時刻列 \(T\) を受け取る（すでに狭義単調増加）。
2. \(i=2\) から \(N\) まで順に、差分 \(d = T_i - T_{i-1}\) を計算する。
3. 差分 \(d\) の最小値 mn と最大値 mx を更新していく。
4. 最後に mn mx を出力する。

隣り合う差分を 1 回ずつ見るだけなので、1 パスで完了します。

計算量

• 時間計算量: \(O(N)\)（差分計算を \(N-1\) 回）
• 空間計算量: \(O(N)\)（時刻列を保持する分。差分だけなら \(O(1)\) でも可能）

実装のポイント

• mn は十分大きい値（例: \(10^{18}\)）で初期化し、mx は 0 で初期化すると更新が簡単です。

• 入力サイズが最大 \(2\times 10^5\) なので、Python では sys.stdin.buffer.read() でまとめて読み取ると高速です。

• 差分は必ず正（\(T_{i} > T_{i-1}\)）なので、最小値・最大値更新が素直に書けます。

  ソースコード

import sys

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    n = data[0]
    t = data[1:1+n]

    mn = 10**18
    mx = 0
    prev = t[0]
    for i in range(1, n):
        d = t[i] - prev
        if d < mn:
            mn = d
        if d > mx:
            mx = d
        prev = t[i]

    sys.stdout.write(f"{mn} {mx}\n")

if __name__ == "__main__":
    main()

この解説は gpt-5.2-high によって生成されました。