概要

直線上に配置された \(N\) 個の基地局すべてが、直接的または間接的に通信できるようにするための最小の通信範囲 \(K\) を求める問題です。

考察

この問題は、グラフ理論の観点では「すべての頂点が連結になるための最小の辺の長さ」を求める問題と言い換えることができます。

重要な気づき

基地局が一直線上にあるため、すべての基地局が互いに通信できるようにするには、隣り合う基地局同士が通信できる状態にすれば十分です。

例えば、座標がソートされた状態で \(X_1, X_2, \dots, X_N\) と並んでいるとき、 - \(X_1\) と \(X_2\) が通信可能（距離 \(\leq K\)） - \(X_2\) と \(X_3\) が通信可能（距離 \(\leq K\)） - … - \(X_{N-1}\) と \(X_N\) が通信可能（距離 \(\leq K\)）

という条件がすべて満たされていれば、どの基地局からどの基地局へも、隣の基地局を中継することで到達可能になります。

最小の \(K\) の決定

すべての隣り合う基地局の間隔を \(D_i = X_{i+1} - X_i\) とすると、通信範囲 \(K\) はすべての \(D_i\) 以上である必要があります（\(K \geq D_i\)）。 この条件をすべての \(i\) について満たす最小の \(K\) は、隣り合う基地局間の距離の最大値となります。

アルゴリズム

1. 基地局の座標 \(X_i\) を昇順にソートします。
2. ソートされた座標において、隣り合う 2 つの基地局の距離 \(X_{i+1} - X_i\) をすべて計算します。
3. それらの距離の中での最大値を求め、出力します。
4. ただし、\(N=1\) の場合は移動する必要がないため、答えは \(0\) となります。

計算量

• 時間計算量: \(O(N \log N)\)
  • 座標のソートに \(O(N \log N)\) かかります。その後の距離の計算と最大値の探索は \(O(N)\) です。
• 空間計算量: \(O(N)\)
  • 基地局の座標を保持するために \(O(N)\) のメモリを使用します。

実装のポイント

• 基地局の座標は必ずしも昇順で与えられるとは限らないため、最初に必ずソートを行う必要があります。

• \(N\) の最大値が \(2 \times 10^5\) と大きいため、Python では sys.stdin.read().split() などを用いて高速に入力を読み込むのが効率的です。

• \(N=1\) のケースでエラーにならないよう、適切に処理を行います（今回のロジックではループが回らないため、初期値を \(0\) とすれば自然に対応可能です）。

  ソースコード

import sys

def solve():
    # 入力をすべて取得
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # 基地局の数 N を取得
    n = int(input_data[0])
    
    # 基地局が1つの場合は通信範囲は 0 で良い
    if n <= 1:
        print(0)
        return
    
    # 基地局の座標 X を取得し、昇順にソートする
    x = list(map(int, input_data[1:]))
    x.sort()
    
    # 隣り合う基地局間の距離の最大値が、求める最小の K となる
    max_diff = 0
    for i in range(n - 1):
        diff = x[i+1] - x[i]
        if diff > max_diff:
            max_diff = diff
            
    # 結果を出力
    print(max_diff)

if __name__ == "__main__":
    solve()

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