概要

街灯の位置をソートし、隣り合う街灯間の距離の最大値を最小化します。
答えを二分探索し、「最大暗区間を \(D\) 以下にできるか？」を判定します。

考察

街灯の位置を小さい順に並べたものを \(A_0, A_1, \ldots, A_{M-1}\) とします。
このとき重要なのは、隣り合う街灯の差

\(A_{i+1} - A_i\)

だけです。

素朴に「どの街灯を動かすか」と「どこへ動かすか」を全探索すると、候補は最大で \(O(MN)\) 個あり、さらに毎回最大値を計算すると間に合いません。

そこで、答えを二分探索します。

「最大暗区間を \(D\) 以下にできるか？」を考えます。

街灯を 1 つ取り除いたとき

ある街灯 \(A_k\) を移動すると考えると、まず \(A_k\) を取り除くことになります。

このとき影響を受ける元の gap は高々 2 つです。

• \(A_{k-1}\) と \(A_k\) の gap
• \(A_k\) と \(A_{k+1}\) の gap

また、\(A_k\) が端でない場合、新しく

\(A_{k+1} - A_{k-1}\)

という gap ができます。

それ以外の gap は変わりません。

移動先に街灯を置いたとき

街灯を 1 つ追加すると、できることは高々 1 つの gap を分割することだけです。

つまり、街灯を取り除いた後に \(D\) を超える gap が 2 個以上ある場合、それらを 1 回の追加で全て直すことはできません。

したがって、各 \(k\) について次のように判定できます。

• 取り除いた後に \(D\) を超える gap が 2 個以上
  → 不可能
• 取り除いた後に \(D\) を超える gap が 1 個
  → その gap の中に街灯を置いて、左右両方の距離を \(D\) 以下にできるか確認
• 取り除いた後に \(D\) を超える gap が 0 個
  → どこかに置いても新しく \(D\) を超える gap を作らなければよい

移動先は元々空いている地点でなければならない

選んだ街灯の元の位置に置き直すことはできません。
そのため、移動先として使えるのは元々空いていた地点だけです。

区間内に空き地点があるかを高速に調べるため、空き地点数の累積和を用意します。

アルゴリズム

まず街灯の位置をソートし、隣り合う差を gap として持ちます。

また、各地点が空いているかを管理し、空き地点数の累積和 prefEmpty を作ります。
これにより、区間 \([l, r]\) に空き地点があるかを \(O(1)\) で判定できます。

判定関数 feasible(D)

「最大暗区間を \(D\) 以下にできるか」を判定します。

まず、現在の gap のうち \(D\) を超えるものを数えます。
これを totalBad とします。

次に、移動する街灯 \(A_k\) を全探索します。

1. \(A_k\) を取り除いた後の悪い gap 数を計算

\(A_k\) を取り除くと、元々の gap のうち

• gap[k-1]
• gap[k]

だけが消えます。

また、\(A_k\) が端でない場合、新しく

\(A_{k+1} - A_{k-1}\)

という gap ができます。

これを使って、取り除いた後に \(D\) を超える gap の個数を求めます。

2. 悪い gap が 2 個以上なら不可能

街灯を 1 つ追加しても、直せる gap は高々 1 個なので、この \(k\) は不可能です。

3. 悪い gap が 1 個の場合

その gap を \([l, r]\) とします。

この gap の中に街灯を置く必要があります。
置く位置を \(x\) とすると、必要条件は

\( x - l \leq D \)

かつ

\( r - x \leq D \)

です。

つまり、

\( r - D \leq x \leq l + D \)

である必要があります。

さらに、\(x\) は gap の内側なので

\( l + 1 \leq x \leq r - 1 \)

です。

よって、置ける範囲は

\( \max(l+1, r-D) \leq x \leq \min(r-1, l+D) \)

です。

この範囲に空き地点があれば、最大暗区間を \(D\) 以下にできます。

4. 悪い gap が 0 個の場合

取り除いた後の街灯たちの最小位置を mn、最大位置を mx とします。

この時点で全ての gap は \(D\) 以下です。

移動先として安全なのは次のいずれかです。

• mn より左に置く
  
  • 新しくできる gap は mn - x
  • よって \(x \in [mn-D, mn-1]\)
• mn と mx の間に置く
  
  • 既存の gap を分割するだけなので、必ず \(D\) 以下になる
  • よって \(x \in [mn+1, mx-1]\)
• mx より右に置く
  
  • 新しくできる gap は x - mx
  • よって \(x \in [mx+1, mx+D]\)

これらの区間のどこかに空き地点があれば可能です。

二分探索

feasible(D) は単調性を持ちます。

つまり、ある \(D\) で可能なら、それより大きい \(D\) でも必ず可能です。

したがって、答えを二分探索できます。

計算量

• 時間計算量: \(O(M \log M + M \log N)\)
  • ソートに \(O(M \log M)\)
  • 二分探索が \(O(\log N)\) 回
  • 各判定が \(O(M)\)
• 空間計算量: \(O(N + M)\)

実装のポイント

• 空き地点の個数を累積和で管理すると、区間内に空き地点があるかを \(O(1)\) で判定できます。

• 移動先は元々空いている地点のみを数えます。移動元の地点は移動先として使えません。

• 端の街灯を取り除く場合は、新しい merged gap が発生しないことに注意します。

• \(M=2\) の場合、街灯を 1 つ取り除くと残りは 1 つになりますが、同じ処理で扱えます。

  ソースコード

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, M;
    cin >> N >> M;

    vector<int> A(M);
    vector<int> occ(N + 1, 0);
    for (int i = 0; i < M; i++) {
        cin >> A[i];
        occ[A[i]] = 1;
    }

    sort(A.begin(), A.end());

    vector<int> gap(M - 1);
    for (int i = 0; i < M - 1; i++) {
        gap[i] = A[i + 1] - A[i];
    }

    vector<int> prefEmpty(N + 1, 0);
    for (int i = 1; i <= N; i++) {
        prefEmpty[i] = prefEmpty[i - 1] + (occ[i] == 0);
    }

    auto countEmpty = [&](int l, int r) -> int {
        l = max(l, 1);
        r = min(r, N);
        if (l > r) return 0;
        return prefEmpty[r] - prefEmpty[l - 1];
    };

    auto feasible = [&](int D) -> bool {
        int totalBad = 0;
        vector<int> badIdx;
        badIdx.reserve(4);

        for (int i = 0; i < M - 1; i++) {
            if (gap[i] > D) {
                totalBad++;
                if ((int)badIdx.size() < 4) badIdx.push_back(i);
            }
        }

        for (int k = 0; k < M; k++) {
            int badUnaffected = totalBad;

            if (k > 0 && gap[k - 1] > D) badUnaffected--;
            if (k + 1 < M && gap[k] > D) badUnaffected--;

            bool mergedBad = false;
            if (k > 0 && k + 1 < M) {
                mergedBad = (A[k + 1] - A[k - 1] > D);
            }

            int badCount = badUnaffected + (mergedBad ? 1 : 0);
            if (badCount > 1) continue;

            if (badCount == 1) {
                int l, r;

                if (mergedBad) {
                    l = A[k - 1];
                    r = A[k + 1];
                } else {
                    if (totalBad > 3) continue;

                    int idx = -1;
                    for (int id : badIdx) {
                        if (id != k - 1 && id != k) {
                            idx = id;
                            break;
                        }
                    }
                    if (idx == -1) continue;

                    l = A[idx];
                    r = A[idx + 1];
                }

                int L = max(l + 1, r - D);
                int R = min(r - 1, l + D);

                if (countEmpty(L, R) > 0) return true;
            } else {
                int mn = (k == 0 ? A[1] : A[0]);
                int mx = (k == M - 1 ? A[M - 2] : A[M - 1]);

                if (countEmpty(mn - D, mn - 1) > 0) return true;
                if (countEmpty(mn + 1, mx - 1) > 0) return true;
                if (countEmpty(mx + 1, mx + D) > 0) return true;
            }
        }

        return false;
    };

    int ok = N, ng = 0;
    while (ok - ng > 1) {
        int mid = (ok + ng) / 2;
        if (feasible(mid)) ok = mid;
        else ng = mid;
    }

    cout << ok << '\n';
    return 0;
}

---

この解説は gpt-5.5-high によって生成されました。