概要

\(N\) 個の集落を \(K\) 個の連続するグループに分割し、各グループの「幅」（最大座標 - 最小座標）の最大値を最小化する問題。答えの \(2\) 倍に対して二分探索を行い、貪欲法で判定する。

考察

重要な観察1: 集落の割り当ては連続するグループになる

集落は数直線上にソートされています。最適な配置では、各避難所に割り当てられる集落は座標順に連続した区間になります。

なぜなら、もし集落 \(A < B < C\) があり、\(A\) と \(C\) が同じ避難所に割り当てられているなら、間にある \(B\) もその避難所に最も近い（か同等に近い）はずだからです。

重要な観察2: 各グループに対する最適な避難所の位置

連続するグループ \(X_l, X_{l+1}, \ldots, X_r\) に対して避難所を1つ配置するとき、最大距離を最小にする位置は中点 \(\frac{X_l + X_r}{2}\) であり、そのときの最大距離は \(\frac{X_r - X_l}{2}\) です。

重要な観察3: 答えの2倍で二分探索

\(d\) が達成可能かを判定する代わりに、\(D = 2d\) （非負整数）に対して二分探索します。条件は「各グループの幅 \(X_r - X_l \leq D\)」となります。

重要な観察4: ちょうど \(K\) グループに分割可能かの判定

• 最小グループ数: 貪欲に各グループをできるだけ大きくする（幅 \(\leq D\) の範囲で右に伸ばす）
• 最大グループ数: 各集落を1つずつ独立グループにすれば \(N\) グループ

最小グループ数 \(\leq K \leq N\) であれば、ちょうど \(K\) グループへの分割が可能です（大きいグループを適宜分割すればよい）。

アルゴリズム

1. \(K \geq N\) なら各集落に避難所を置けるので答えは \(0\)
2. \(D = 2d\) に対して二分探索（\(0 \leq D \leq 2(X_N - X_1)\)）
3. 各 \(D\) に対し、貪欲法で最小グループ数を計算：
   • 左から順に見て、現在のグループの先頭からの幅が \(D\) を超えたら新しいグループを開始
4. 最小グループ数 \(\leq K\) なら \(D\) は達成可能

具体例: \(N=5, K=2, X=[1, 3, 7, 8, 12]\), \(D=4\) の場合 - グループ1: \(\{1, 3\}\)（幅 \(2 \leq 4\)）、\(7\) を追加すると幅 \(6 > 4\) なのでここで切る - グループ2: \(\{7, 8, 12\}\)（幅 \(5 > 4\)）、\(12\) を追加すると超えるので切る - 最小グループ数 = 3 > 2 → \(D=4\) では不十分

計算量

• 時間計算量: \(O(N \log(\max(X_i)))\) — 二分探索が \(O(\log(2 \cdot 10^9))\) 回、各判定が \(O(N)\)
• 空間計算量: \(O(N)\)

実装のポイント

• 二分探索の対象は \(2d\)（非負整数）であるため、整数上の二分探索で正確に求まる

• 答えが半整数になるケースも \(2d\) を整数として扱うことで自然に処理できる

• 貪欲法では「現在のグループの先頭」を記録し、新しい集落との差が \(D\) を超えたら新グループを開始する

  ソースコード

import sys
from typing import List

def solve():
    input_data = sys.stdin.buffer.read().split()
    N = int(input_data[0])
    K = int(input_data[1])
    X = [int(input_data[i + 2]) for i in range(N)]
    
    if K >= N:
        print(0)
        return
    
    # Binary search on 2d (let's call it D = 2d)
    # So d = D/2, and each shelter covers a range of length d on each side.
    # We need to check: can we partition N settlements into K contiguous groups,
    # where each group can be covered by one shelter with max distance <= d = D/2,
    # AND every shelter has at least one settlement assigned to it.
    
    # For a contiguous group of settlements X[l], X[l+1], ..., X[r],
    # the optimal shelter is at (X[l] + X[r]) / 2, and the max distance is (X[r] - X[l]) / 2.
    # So the condition is X[r] - X[l] <= D (since 2d = D means d = D/2, and we need (X[r]-X[l])/2 <= D/2).
    # Wait, (X[r] - X[l]) / 2 <= d = D/2, so X[r] - X[l] <= D.
    
    # But we also need ALL K shelters to have at least 1 settlement.
    # So we must partition into EXACTLY K groups (each non-empty, contiguous).
    
    # Greedy check: given D, can we partition N sorted settlements into exactly K contiguous groups
    # such that each group has span <= D?
    
    # Greedy: go left to right, extend current group as far as possible. Count min groups needed.
    # Also count max groups possible (each group is 1 settlement except when forced).
    # We need min_groups <= K <= max_groups.
    
    # min_groups: greedily make groups as large as possible
    # max_groups: greedily make groups as small as possible (each group = 1 settlement, 
    #             but we must ensure remaining can be covered... actually max_groups = N if D >= 0 always,
    #             since each settlement can be its own group with span 0 <= D for D >= 0)
    # Wait, but K <= N, so max_groups = N always works if D >= 0.
    # So we just need min_groups <= K.
    
    # Actually wait - we need exactly K groups, and each group must have span <= D.
    # min_groups is the minimum number of groups needed. If min_groups <= K, 
    # since we can always split a group into smaller groups (max_groups = N),
    # and K <= N, we can achieve exactly K groups.
    # But we need to be careful: can we always split groups freely?
    # Yes, because groups are contiguous and each single settlement forms a valid group (span 0 <= D).
    # So if min_groups <= K <= N, it's feasible.
    
    def min_groups(D):
        # Minimum number of contiguous groups where each group has X[r] - X[l] <= D
        count = 1
        left = 0
        for right in range(1, N):
            if X[right] - X[left] > D:
                count += 1
                left = right
        return count
    
    # Binary search on D (= 2d), which is a non-negative integer.
    # We need min_groups(D) <= K.
    
    lo, hi = 0, 2 * (X[-1] - X[0])
    
    while lo < hi:
        mid = (lo + hi) // 2
        if min_groups(mid) <= K:
            hi = mid
        else:
            lo = mid + 1
    
    print(lo)

solve()

---

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