概要

一直線上にある基地局を、距離 \(K\) 以下なら直接通信できるとして「全体が連結」になる最小の \(K\) を求めます。結論として、座標を昇順に並べたときの隣り合う基地局間の距離の最大値が答えになります。

考察

基地局を頂点、距離が \(K\) 以下のペアに辺を張ったグラフを考えると、「任意の2局が中継を経て通信できる」ことは グラフが連結であることと同じです。

ここで基地局が一直線上にあることが重要です。座標を小さい順に並べて \(X_{(1)} < X_{(2)} < \dots < X_{(N)}\) とします。

• もしどこかに隣接差分 \(X_{(i+1)} - X_{(i)} > K\) が存在すると、その“すき間”を直接越えられません。
  さらに一直線上なので、左側の点から右側の点へ行くには必ずこの区間を跨ぐ必要があり、グラフは必ず分断されます（連結になれない）。
• 逆に、すべての隣接差分が \(X_{(i+1)} - X_{(i)} \le K\) なら、隣り合う基地局同士が全て直接通信できます。
  すると \(X_{(1)} \leftrightarrow X_{(2)} \leftrightarrow \dots \leftrightarrow X_{(N)}\) という鎖（パス）ができ、全体が連結になります。

よって「連結になる条件」は
$\(\max_{i}(X_{(i+1)} - X_{(i)}) \le K\)\( であり、最小の \)K\( は \)\(K_{\min} = \max_{i}(X_{(i+1)} - X_{(i)})\)$
です。

素朴解が不利な理由

例えば「\(K\) を二分探索して、そのたびにグラフを作って BFS/DFS で連結判定する」ような方法も考えられます。しかし辺の数が最大で \(O(N^2)\) になり得て重く、実際には本問ではもっと単純な一次元の性質により 最大隣接差分だけで答えが決まるため、過剰です。

具体例

座標が \([1, 3, 8, 10]\) のとき、隣接差分は \(2, 5, 2\) なので最大は \(5\)。
\(K=4\) だと \(3\) と \(8\) が繋がらず分断されますが、\(K=5\) なら全て鎖状に繋がり連結になります。

アルゴリズム

1. \(N \le 1\) なら基地局が1つ以下なので、通信範囲は不要で \(0\) を出力。
2. 座標配列 \(X\) を昇順にソートする。
3. 隣り合う差分 \(X[i+1]-X[i]\) を全て調べ、その最大値を答えとして出力する。

計算量

• 時間計算量: ソートが支配的で \(O(N \log N)\)
• 空間計算量: 入力配列などで \(O(N)\)

実装のポイント

• 座標はバラバラに与えられるので 必ずソートしてから隣接差分を取ります。

• \(N=1\) のときは差分が定義できないため、特別に \(0\) を出力します。

• 差分は最大で \(10^9\) 程度なので、Python の int で安全に扱えます。

  ソースコード

import sys

def main():
    input = sys.stdin.readline
    N = int(input().strip())
    X = list(map(int, input().split()))
    if N <= 1:
        print(0)
        return
    X.sort()
    ans = 0
    for i in range(N - 1):
        d = X[i + 1] - X[i]
        if d > ans:
            ans = d
    print(ans)

if __name__ == "__main__":
    main()

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