概要

一直線上に配置された基地局同士がすべて通信できるようにするために必要な、最小の通信範囲 \(K\) を求める問題。

考察

この問題では、すべての基地局が「直接または中継によって」通信できるネットワークを構築する必要がある。つまり、グラフ理論で言うところの「連結グラフ」を作ることが目的である。

素朴な方法としては、ある \(K\) を仮定し、その \(K\) で全基地局が連結になるかどうかを判定するという二分探索的なアプローチが考えられる。しかし、もっと効率的に解く方法がある。

重要な観察は、「基地局が一直線上に並んでいる」ことと、「通信可能かどうかは距離 \(K\) 以内かどうかで決まる」という点である。つまり、隣接する基地局同士が通信できれば、全体が連結になる可能性が高い。

実際に、基地局を座標順にソートした上で、隣り合う基地局同士の距離の最大値が、最小の \(K\) となる。なぜなら、その最大の距離さえカバーできれば、それより短い距離は自動的にカバーされるため、すべての基地局が連結になるからである。

たとえば、座標が [1, 4, 7] で並んでいる場合、隣接距離は \(3\) ずつなので、最小の \(K\) は \(3\) となる。これより小さいと、例えば \(K=2\) では1番と2番の基地局は通信できるが、2番と3番も通信できるものの、1番と3番が直接も中継もできないため、ネットワークが切断されてしまう。

逆に、隣接する基地局の最大距離を \(K\) とすれば、どの基地局も「前後の基地局と通信できる」ので、最終的にすべての基地局が連結されることが保証される。

アルゴリズム

1. 基地局の座標リスト \(X\) をソートする。
2. ソートされたリストにおいて、隣接要素間の差分 \(|X[i] - X[i-1]|\) を計算し、その最大値を求める。
3. その最大値が求める最小の通信範囲 \(K\) である。

計算量

• 時間計算量: \(O(N \log N)\)（ソートが支配的）
• 空間計算量: \(O(1)\)（入力を除けば定数メモリ）

実装のポイント

• 入力の受け取りと座標のソートを忘れない。
• 差分を取るときにインデックスに注意（最初の要素は比較相手がない）。
• 整数型での計算で十分な精度があるため、特に浮動小数点数は不要。

## ソースコード

```python
def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    N = int(data[0])
    X = list(map(int, data[1:]))
    
    # 座標をソート
    X.sort()
    
    # 隣接する基地局間の距離の最大値が求める最小のK
    max_diff = 0
    for i in range(1, N):
        diff = X[i] - X[i-1]
        if diff > max_diff:
            max_diff = diff
    
    print(max_diff)

if __name__ == "__main__":
    main()

この解説は qwen3-coder-480b によって生成されました。