概要

この問題は、東西に並ぶ \(N\) 個の地点のうち \(M\) 個に設置された街灯から、ちょうど1つを選んで別の空き地点に移動させることで、隣り合う街灯の間の最大距離（最大暗区間）を最小化する問題です。

「最大暗区間を \(X\) 以下にできるか？」という判定問題を解くことで、答えの二分探索を用いて最適な最小値を求めることができます。

---

考察

1. 答えの二分探索

「最大暗区間を \(X\) 以下にできるか？」という条件は、単調性を持っています。 もし最大暗区間を \(X\) 以下にできるなら、それより大きい任意の \(Y > X\) に対しても当然 \(Y\) 以下にできます。 したがって、求める最小値を二分探索（Binary Search）によって求めることができます。 探索範囲は、最小値が \(1\)、最大値が \(N\) です。

2. 判定問題：最大暗区間を \(X\) 以下にできるか？

街灯の座標を昇順にソートして \(A_1 < A_2 < \dots < A_M\) とし、隣り合う街灯の間隔を \(D_i = A_{i+1} - A_i\) （\(1 \le i \le M-1\)）とします。

どの街灯を動かすかを全探索します。動かす街灯を \(A_k\) （\(1 \le k \le M\)）と固定しましょう。 街灯 \(A_k\) を取り除いたとき、残った \(M-1\) 個の街灯の間隔のうち、\(X\) を超えているものの個数を \(G\) とします。

街灯 \(A_k\) を取り除いた後の間隔は、元の間隔 \(D\) から以下のように変化します。 - \(k=1\) のとき: \(D_1\) が消滅する。 - \(k=M\) のとき: \(D_{M-1}\) が消滅する。 - \(1 < k < M\) のとき: \(D_{k-1}\) と \(D_k\) が消滅し、代わりに新たな間隔 \(D_{k-1} + D_k\) が発生する。

これ以外の間隔は変化しません。 もともと \(D_i > X\) であったインデックスの集合をあらかじめリストアップしておけば、各 \(k\) に対する \(G\) の値を \(O(1)\) で計算できます。 （※ もともと \(D_i > X\) となる箇所が 4 つ以上ある場合、どの街灯を動かしても \(G \ge 2\) となるため、即座に「不可能」と判定して枝刈りできます）

\(G\) の値に応じて、街灯 \(A_k\) を配置できる空き地が存在するかを判定します。

ケース1: \(G \ge 2\) の場合

\(X\) を超える区間が 2 つ以上残っているため、1 つの街灯 \(A_k\) をどこに配置してもすべての区間を \(X\) 以下にすることはできません。よって、この \(k\) では不可能です。

ケース2: \(G = 1\) の場合

\(X\) を超える区間がちょうど 1 つだけ存在します。その区間の左端を \(L_{val}\)、右端を \(R_{val}\) とします。 この区間の間に \(A_k\) を配置して、2 つに分割された区間の長さがともに \(X\) 以下になるようにしなければなりません。 すなわち、配置する座標 \(P\) は以下の条件を満たす必要があります。 - \(L_{val} < P < R_{val}\) （区間の内側） - \(P - L_{val} \le X \iff P \le L_{val} + X\) - \(R_{val} - P \le X \iff P \ge R_{val} - X\)

これらをまとめると、 $\(\max(L_{val} + 1, R_{val} - X) \le P \le \min(R_{val} - 1, L_{val} + X)\)\( を満たす空き地 \)P\( が存在すれば、この \)k$ は可能です。

ケース3: \(G = 0\) の場合

すでに残ったすべての街灯の間隔が \(X\) 以下です。 この場合、街灯 \(A_k\) をどこかに配置した結果、新たな間隔が \(X\) を超えないようにすればよいです。 残った街灯の最小値を \(B_1\)、最大値を \(B_{M-1}\) とすると、配置できる場所 \(P\) は以下のいずれかです。

1. 左端の外側: \(B_1\) の左側。間隔が \(X\) 以下であるためには \(B_1 - X \le P \le B_1 - 1\)。
2. 右端の外側: \(B_{M-1}\) の右側。間隔が \(X\) 以下であるためには \(B_{M-1} + 1 \le P \le B_{M-1} + X\)。
3. 内側: \(B_1\) と \(B_{M-1}\) の間。すでにこの間の街灯の間隔はすべて \(X\) 以下なので、その間のどこに置いても間隔がさらに細分化されるだけなので、常に \(X\) 以下に保たれます。すなわち \(B_1 + 1 \le P \le B_{M-1} - 1\)。

これらのいずれかの範囲に空き地 \(P\) が存在すれば、この \(k\) は可能です。

3. 空き地の存在判定

ある範囲 \([L, R]\) に空き地（街灯が置かれていない地点）が存在するかどうかは、累積和を用いることで \(O(1)\) で判定できます。 各地点 \(i\) について、街灯がなければ \(1\)、街灯があれば \(0\) とする配列 IsU を作成し、その累積和 SumU を計算しておきます。 区間 \([L, R]\) に空き地が存在することは、SumU[R] - SumU[L-1] > 0 と同値です。

---

アルゴリズム

1. 入力と前処理:
   • 街灯の座標 \(S\) をソートして配列 \(A\) とする。
   • 各地点が空き地かどうかを表す配列 IsU を作り、その累積和 SumU を計算する。
   • 隣り合う街灯の距離の配列 \(D\) を計算する。
2. 二分探索:
   • 探索範囲を \(low = 1, high = N\) とし、その中央値 \(mid\) について判定関数 check(mid) を呼ぶ。
3. 判定関数 check(X):
   • \(D_i > X\) となるインデックスを収集する。これが 4 つ以上なら false を返す。
   • 各街灯 \(k = 1 \dots M\) について以下を行う：
     • \(A_k\) を除いたときの「\(X\) を超える間隔の数」 \(G\) を求める。
     • \(G = 1\) の場合、超えている区間の間に収まる空き地が存在するかを累積和で判定する。
     • \(G = 0\) の場合、端の外側または内側に配置できる空き地が存在するかを累積和で判定する。
     • 条件を満たす空き地が見つかれば true を返す。
   • すべての \(k\) で不可能なら false を返す。

---

計算量

• 時間計算量: \(O(M \log M + N + M \log N)\)

  • 街灯のソートに \(O(M \log M)\)。
  • 累積和の構築に \(O(N)\)。
  • 二分探索のステップ数は \(O(\log N)\) 回。
  • 判定関数 check(X) は、各ステップで \(M\) 個の街灯を走査し、各判定は \(O(1)\) なので全体で \(O(M)\)。
  • したがって、全体の時間計算量は十分に実行時間制限に間に合います。

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

  • 座標配列や累積和配列を保持するために \(O(N)\) のメモリを使用します。

---

実装のポイント

• 元の位置への配置の除外:

  • 問題文より「必ずちょうど1つの街灯を別の空き地点に移設」する必要があります。
  • 動かす街灯 \(A_k\) の元の位置は、累積和 SumU において IsU[A[k]] = 0 （空き地ではない）となっているため、自然に選択肢から除外されます。これにより「移設しない」という無効な遷移を綺麗に防ぐことができます。

• インデックスの境界:

  • 空き地を探索する範囲 \([L, R]\) が、道路の範囲 \([1, N]\) をはみ出さないように max(1, L) や min(N, R) で適切にクリップする必要があります。

    ソースコード

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

using namespace std;

int N, M;
vector<int> A;
vector<int> D;
vector<int> SumU;

bool has_U(int L, int R) {
    if (L > R) return false;
    L = max(1, L);
    R = min(N, R);
    if (L > R) return false;
    return (SumU[R] - SumU[L-1]) > 0;
}

bool check(int X) {
    vector<int> bad_indices;
    for (int i = 1; i <= M - 1; ++i) {
        if (D[i] > X) {
            bad_indices.push_back(i);
            if (bad_indices.size() > 3) return false;
        }
    }
    int cnt = bad_indices.size();

    for (int k = 1; k <= M; ++k) {
        int G = cnt;
        if (k == 1) {
            if (D[1] > X) G--;
        } else if (k == M) {
            if (D[M-1] > X) G--;
        } else {
            if (D[k-1] > X) G--;
            if (D[k] > X) G--;
            if (D[k-1] + D[k] > X) G++;
        }

        if (G >= 2) continue;

        if (G == 1) {
            int L_val = -1, R_val = -1;
            if (1 < k && k < M && D[k-1] + D[k] > X) {
                L_val = A[k-1];
                R_val = A[k+1];
            } else {
                int idx = -1;
                for (int i : bad_indices) {
                    if (k == 1 && i == 1) continue;
                    if (k == M && i == M - 1) continue;
                    if (1 < k && k < M && (i == k - 1 || i == k)) continue;
                    idx = i;
                    break;
                }
                if (idx != -1) {
                    L_val = A[idx];
                    R_val = A[idx+1];
                }
            }
            if (L_val != -1 && R_val != -1) {
                int L_range = max(L_val + 1, R_val - X);
                int R_range = min(R_val - 1, L_val + X);
                if (has_U(L_range, R_range)) return true;
            }
        } else { // G == 0
            int B1, BM_minus_1;
            if (k == 1) {
                B1 = A[2];
                BM_minus_1 = A[M];
            } else if (k == M) {
                B1 = A[1];
                BM_minus_1 = A[M-1];
            } else {
                B1 = A[1];
                BM_minus_1 = A[M];
            }

            if (has_U(B1 - X, B1 - 1)) return true;
            if (has_U(BM_minus_1 + 1, BM_minus_1 + X)) return true;
            if (has_U(B1 + 1, BM_minus_1 - 1)) return true;
        }
    }
    return false;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    if (!(cin >> N >> M)) return 0;

    A.resize(M + 1);
    for (int i = 1; i <= M; ++i) {
        cin >> A[i];
    }
    sort(A.begin() + 1, A.end());

    D.resize(M);
    for (int i = 1; i <= M - 1; ++i) {
        D[i] = A[i+1] - A[i];
    }

    vector<int> IsU(N + 1, 1);
    IsU[0] = 0;
    for (int i = 1; i <= M; ++i) {
        IsU[A[i]] = 0;
    }
    SumU.resize(N + 1, 0);
    for (int i = 1; i <= N; ++i) {
        SumU[i] = SumU[i-1] + IsU[i];
    }

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

    cout << ans << "\n";

    return 0;
}

---

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