概要

この問題は、数直線上の \(N\) 個の集落を \(K\) 個以下のグループに分割し、各グループ内の集落の座標の最大値と最小値の差（の半分）を最小化する問題です。「最大値の最小化」という典型的な構造を持っているため、答えを二分探索する手法（通称：決め打ち二分探索）を用いて効率的に解くことができます。

考察

1. 問題の言い換え

各避難所がカバーする集落の集合を「グループ」と呼びます。 ある避難所がカバーする集落の最小の座標を \(X_L\)、最大の座標を \(X_R\) とします。このグループのすべての集落から避難所までの距離を最小にするには、避難所を \(X_L\) と \(X_R\) のちょうど中間地点 \(P = \frac{X_L + X_R}{2}\) に設置するのが最適です。

このとき、グループ内の任意の集落から避難所までの距離は、最大でも \(\frac{X_R - X_L}{2}\) となります。 したがって、「各集落から避難所までの最大距離を \(d\) 以下にする」という条件は、「各グループの（最大座標 \(-\) 最小座標）を \(2d\) 以下にする」と言い換えることができます。

2. 「受入数 1 以上」と「避難所数 \(K\) 個」の条件について

問題文には「避難所をちょうど \(K\) 個設置し、すべての避難所の受入数を 1 以上にする」という条件があります。一見複雑そうに見えますが、以下のようにシンプルに考えることができます。

もし、最大距離の制限を満たすように集落をグループ分けした結果、グループ数が \(K\) 未満（例えば \(M\) 個、ただし \(M < K\)）になったとします。 この場合、余った \(K - M\) 個の避難所は、すでにグループに含まれている集落の「すぐ隣（実数座標なので、極めて近い位置）」に設置すればよいです。これにより、既存の割り当てや最大距離に影響を与えることなく、避難所の数を \(K\) 個に増やし、かつすべての受入数を 1 以上にすることができます。

したがって、この条件は実質的に「集落を \(K\) 個以下のグループに分割できるか」という条件に簡略化されます。

3. なぜ二分探索なのか？

求めたい \(2d\) の値を \(W\) とします。 * \(W\) が小さすぎる（例: \(W = 0\)）と、各グループに 1 つの集落しか入れられず、必要な避難所の数が \(N\) 個になってしまい、\(K\) 個以下に収まりません。 * \(W\) が十分大きい（例: \(W = X_N - X_1\)）と、すべての集落を 1 つのグループにまとめられるため、避難所は 1 個で済みます。

このように、「\(W\) 以上であれば条件を満たすグループ分けが可能である」という判定結果には単調性（ある値を境に、それより大きければ常に可能、小さければ常に不可能になる性質）が存在します。そのため、二分探索を用いて最適な \(W\)（すなわち \(2d\) の最小値）を求めることができます。

アルゴリズム

二分探索の各ステップにおいて、「最大距離の 2 倍が \(W\) 以下となるように、集落を \(K\) 個以下のグループに分割できるか？」という判定問題を貪欲法（Greedy）で解きます。

判定アルゴリズム（貪欲法）

左端の集落から順にグループを決めていきます。 1. 現在のグループの左端の集落を \(X_L\) とします。 2. このグループに入れられる右端の集落 \(X_R\) は、距離の制限から \(X_R \le X_L + W\) を満たす必要があります。できるだけ多くの集落を同じグループに入れた方が有利なので、この条件を満たす最大の \(R\) を選びます。 3. 次のグループの左端を \(X_{R+1}\) として、同様の操作を繰り返します。 4. すべての集落をカバーし終えたときのグループ数が \(K\) 以下であれば「判定成功」、\(K\) を超えてしまえば「判定失敗」とします。

条件を満たす最大の \(R\) を探す処理は、ソート済みの配列 \(X\) に対して二分探索（Python では bisect_right）を使用することで高速に行うことができます。

計算量

• 時間計算量: \(O(N \log N \log(\max X))\)

  • 二分探索の範囲は \(0\) から \(X_N - X_1\)（最大約 \(10^9\)）です。ループ回数は \(\log_2(10^9) \approx 30\) 回となります。
  • 各判定処理では、左端 \(L\) から順に bisect_right を用いて右端 \(R\) を探索します。最悪の場合でも \(N\) 回の二分探索が行われるため、1回の判定にかかる時間は \(O(N \log N)\) です。
  • したがって、全体の計算量は \(O(N \log N \log(\max X))\) となり、実行時間制限に十分間に合います。

• 空間計算量: \(O(N)\)

  • 集落の座標を格納する配列 \(X\) の分のメモリのみを使用します。

実装のポイント

• bisect_right を呼び出す際、引数に lo=L を指定することで、探索の開始位置を現在の左端 \(L\) に制限しています。これにより、無駄な探索を省き実行時間をさらに短縮することができます。

• 問題文で保証されている通り、\(2d\) は必ず整数になるため、二分探索の探索範囲（low, high, mid）はすべて整数型で完結させることができます。

  ソースコード

import sys
import bisect

def solve():
    # 入力を一括取得
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    N = int(input_data[0])
    K = int(input_data[1])
    
    X = [int(x) for x in input_data[2:]]
    
    # 二分探索の範囲
    low = 0
    high = X[-1] - X[0]
    ans = high
    
    while low <= high:
        mid = (low + high) // 2
        
        # 判定
        count = 0
        L = 0
        possible = True
        while L < N:
            count += 1
            if count > K:
                possible = False
                break
            target = X[L] + mid
            # X[L] + mid 以下の最大の要素のインデックス R を探す
            R = bisect.bisect_right(X, target, lo=L) - 1
            L = R + 1
            
        if possible:
            ans = mid
            high = mid - 1
        else:
            low = mid + 1
            
    print(ans)

if __name__ == '__main__':
    solve()

---

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