概要

この問題は、数直線上の \(N\) 個の集落に対して \(K\) 個の避難所を配置し、各集落から最も近い避難所までの距離の最大値 \(d\) を最小化する問題です。

「最大値の最小化」という典型的な構造に着目し、答え（距離の \(2\) 倍である \(2d\)）を二分探索することで、効率的に最適解を求めることができます。

---

考察

1. 避難所がカバーできる範囲

避難所の座標を \(P\)、許容する最大距離を \(d\) とします。この避難所がカバーできる集落の座標 \(X_i\) は、以下の範囲に存在する必要があります。 $\(P - d \leq X_i \leq P + d\)$

この区間の左端から右端までの最大の長さ（幅）は、\((P + d) - (P - d) = 2d\) となります。 つまり、「最大距離が \(d\) 以下である」ということは、「各避難所がカバーする集落の集合において、最も右の集落と最も左の集落の距離が \(2d\) 以下である」ことと同値です。

ここで \(D = 2d\) とおくと、問題は「集落をいくつかのグループに分けたとき、各グループ内の（最大座標 \(-\) 最小座標）がすべて \(D\) 以下となるようにできるか？」という問題に言い換えられます。

2. 「すべての避難所の受入数が 1 以上」という条件

避難所はちょうど \(K\) 個設置する必要があります。 もし、最大幅 \(D\) のグループに分けたときの最小のグループ数が \(cnt\) だったとします。 - \(cnt > K\) の場合：幅 \(D\) を保ったまま \(K\) 個以下のグループに分けることは不可能です。よって、最大距離 \(d = D/2\) は達成不可能です。 - \(cnt \leq K\) の場合：幅 \(D\) を保ったまま \(K\) 個のグループに分けることが可能です。なぜなら、要素数が \(2\) 以上のグループをさらに細かく分割していけば、グループ内の最大幅は \(D\) 以下のまま、グループ数をちょうど \(K\) 個に増やすことができるからです（\(K \leq N\) なので必ず可能です）。

したがって、ある \(D\) に対して、「幅 \(D\) 以下の区間で集落をカバーするとき、必要な区間の最小数が \(K\) 以下であるか？」 という判定問題を解けばよいことになります。

3. 判定問題の解き方（貪欲法）

「幅 \(D\) 以下の区間で、すべての集落をカバーする最小の区間数」は、左から貪欲に決めることで求められます。 1. まだカバーされていない最も左の集落の座標を \(L\) とします。 2. \(L\) を左端とする幅 \(D\) の区間 \([L, L+D]\) を考えます。 3. この区間に含まれる集落をすべて同じ避難所でカバーします。 4. まだカバーされていない集落が残っていれば、1 に戻り、新しい区間を作成します。

この方法で求めた区間数 \(cnt\) が \(K\) 以下であれば、その \(D\) は達成可能です。

4. 単調性と二分探索

「幅 \(D\) が大きくなればなるほど、必要な区間数 \(cnt\) は小さくなる（または変わらない）」という単調性が成り立ちます。 したがって、求める最小の \(D\) について二分探索を行うことができます。

---

アルゴリズム

1. 二分探索の範囲を設定する

   • 最小値 low = 0
   • 最大値 high = X[N-1] - X[0] （すべての集落を 1 つの避難所でカバーする場合の最大幅）

2. 二分探索を行う

   • mid = (low + high) / 2 とし、check(mid) を呼び出す。
   • check(mid) が true （\(K\) 個以下でカバー可能）なら、さらに小さい \(D\) を試すため、high = mid - 1 とする。
   • check(mid) が false なら、より大きな \(D\) が必要なので、low = mid + 1 とする。

3. 判定関数 check(D) の実装

   • 左端の集落から順に、現在の区間の左端 \(L\) からの距離が \(D\) を超えるまで集落を同じグループに含める。
   • 超えたら新しいグループを作成し、その集落を新たな左端 \(L\) とする。
   • 最終的なグループ数 \(cnt\) が \(K\) 以下なら true、そうでなければ false を返す。

---

計算量

• 時間計算量: \(O(N \log (\max X_i))\) 二分探索のステップ数は \(O(\log(\max X_i))\) です。制約より座標の最大値は \(10^9\) なので、ループ回数は約 \(30\) 回です。各ステップでの判定関数 check は、集落を左から右に 1 走査するだけなので \(O(N)\) です。 全体の計算量は \(O(N \log (\max X_i))\) となり、十分に高速です（\(N = 2 \times 10^5\) でも約 \(6 \times 10^6\) 回の計算で済み、実行時間制限に余裕で間に合います）。

• 空間計算量: \(O(N)\) 集落の座標 \(X_1, \dots, X_N\) を保持するための配列のメモリ領域のみが必要です。

---

実装のポイント

• 整数での処理: 問題文では「距離 \(d\) は整数または半整数になり、\(2d\) は必ず非負整数になる」とあります。 最初から \(D = 2d\) という「距離の2倍」の値を探索の対象とすることで、実数（double など）を一切使わずに、すべて整数型（long long）のみで誤差なく処理することができます。

• 高速入出力: C++では \(N = 2 \times 10^5\) と入力が大きいため、std::ios_base::sync_with_stdio(false); std::cin.tie(NULL); を用いて入出力を高速化しています。

  ソースコード

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    // 標準入出力の高速化
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N, K;
    if (!(cin >> N >> K)) return 0;

    vector<long long> X(N);
    for (int i = 0; i < N; ++i) {
        cin >> X[i];
    }

    // 距離の2倍である D に対する判定関数
    auto check = [&](long long D) {
        int cnt = 0;
        int i = 0;
        while (i < N) {
            cnt++;
            long long L = X[i];
            // スパンが D 以下である限り、同じ区間に含める
            while (i < N && X[i] - L <= D) {
                i++;
            }
        }
        return cnt <= K;
    };

    // 二分探索
    long long low = 0, high = X[N - 1] - X[0];
    long long ans = high;

    while (low <= high) {
        long long mid = low + (high - low) / 2;
        if (check(mid)) {
            ans = mid;
            high = mid - 1;
        } else {
            low = mid + 1;
        }
    }

    cout << ans << "\n";

    return 0;
}

---

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