概要

一直線上に並んだ基地局をすべて連結するために必要な最小の通信範囲 \(K\) を求める問題です。これは隣接する基地局間の距離の最大値を求めることに帰着されます。

考察

重要な気づき

基地局が一直線上に並んでいるという点がポイントです。すべての基地局を連結するためには、座標でソートしたときの「隣り合う基地局同士」が通信できれば十分です。

例えば、座標が \(1, 5, 8\) の3つの基地局があるとします。 - 基地局1（座標1）と基地局2（座標5）の距離: \(4\) - 基地局2（座標5）と基地局3（座標8）の距離: \(3\)

この場合、\(K = 4\) であれば、1→2→3 と中継して全員が通信できます。

なぜ隣接間だけを見ればよいか

座標をソートした後、隣接する基地局が全てつながっていれば、鎖のように全体が連結されます。逆に、どこか1箇所でも隣接間がつながっていなければ、ネットワークは分断されてしまいます。

具体的には、座標 \(X_i\) と \(X_{i+1}\) の間にある基地局は存在しないため、この2つを直接つなぐ以外に方法がありません。

素朴なアプローチの問題点

すべてのペア \((i, j)\) について距離を計算し、グラフとして連結性を判定する方法では、\(O(N^2)\) の計算量がかかり、\(N = 2 \times 10^5\) では間に合いません。

解決策

座標をソートして、隣接する基地局間の距離（ギャップ）の最大値を求めれば、それが答えになります。

アルゴリズム

1. 基地局が1つだけの場合、通信範囲は \(0\) でよい（出力して終了）
2. 座標をソートする
3. 隣接する基地局間の距離を全て計算し、その最大値を求める
4. 最大値を出力する

例: X = [8, 1, 5] の場合
ソート後: X = [1, 5, 8]
ギャップ: 5-1=4, 8-5=3
最大ギャップ: 4
答え: K = 4

計算量

• 時間計算量: \(O(N \log N)\)（ソートが支配的）
• 空間計算量: \(O(N)\)（座標を格納する配列）

実装のポイント

• \(N = 1\) の特殊ケース: 基地局が1つしかない場合、他と通信する必要がないため \(K = 0\) を出力する

• ソートを忘れない: 入力は座標順に並んでいるとは限らないので、必ずソートする

• 整数演算で十分: 座標は整数で与えられ、距離も整数になるため、浮動小数点数を使う必要はない

  ソースコード

def solve():
    N = int(input())
    X = list(map(int, input().split()))
    
    if N == 1:
        print(0)
        return
    
    # Sort the coordinates
    X.sort()
    
    # Find the maximum gap between consecutive stations
    max_gap = 0
    for i in range(1, N):
        gap = X[i] - X[i-1]
        max_gap = max(max_gap, gap)
    
    print(max_gap)

solve()

---

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