概要

街灯の位置をソートし、隣り合う街灯間の差だけを考えます。
「最大暗区間を \(D\) 以下にできるか」を判定する関数を作り、答えを二分探索で求めます。

考察

街灯の位置を小さい順に並べたものを

\(A_0, A_1, \ldots, A_{M-1}\)

とします。隣り合う街灯間の差を

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

とすると、現在の最大暗区間は \(G_i\) の最大値です。

素朴な方法が難しい理由

「どの街灯を動かすか」は \(M\) 通り、「どこへ動かすか」は最大 \(N\) 通りあります。
各移動後に最大暗区間を計算すると、最悪で \(O(MN)\) 以上かかり、\(N,M \leq 3 \times 10^5\) では間に合いません。

\(D\) 以下にできるかを判定する

答えを直接求める代わりに、

ちょうど \(1\) つ街灯を移動して、すべての隣接差を \(D\) 以下にできるか？

を判定します。

もし \(D\) 以下にできるなら、\(D+1\) 以上でも当然できます。
したがって、この判定は単調性を持つので、二分探索が使えます。

悪い隙間

固定した \(D\) に対して、\(G_i > D\) である隙間を「悪い隙間」と呼びます。

街灯を \(1\) つ移動するとき、操作は次の \(2\) 段階で考えられます。

1. ある街灯を取り除く
2. その街灯を空いている別の地点に置く

街灯を取り除くと、影響を受ける隙間はその街灯の左右だけです。

例えば、内部の街灯 \(A_i\) を取り除くと、

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

の \(2\) つの隙間が消え、代わりに

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

という新しい隙間ができます。

一方、街灯を置く操作で直せる隙間は高々 \(1\) つです。
つまり、取り除いた後に悪い隙間が \(2\) つ以上残っていると、その \(D\) は不可能です。

また、最初から悪い隙間が \(3\) つ以上ある場合も不可能です。
なぜなら、街灯を \(1\) つ取り除いても、悪い隙間を十分には減らせないためです。

悪い隙間を分割できる条件

悪い隙間が \((u, v)\)、つまり左の街灯が \(u\)、右の街灯が \(v\) にあるとします。

この隙間を新しい街灯 \(x\) で分割して、両方の差を \(D\) 以下にするには、

\(u < x < v\)

かつ

\(x - u \leq D\)

\(v - x \leq D\)

である必要があります。

したがって、\(x\) が置ける範囲は

\(L = \max(u+1, v-D)\)

\(R = \min(v-1, u+D)\)

です。

この区間 \([L, R]\) に、元々空いている地点が存在すれば、その悪い隙間を直せます。

アルゴリズム

まず前処理をします。

1. 街灯の位置をソートして配列 \(A\) にする
2. 隣接差 \(G_i = A_{i+1} - A_i\) を作る
3. 各地点が埋まっているかを表す配列を作る
4. 累積和 pref を作り、任意の区間 \([l,r]\) に空き地点があるかを \(O(1)\) で判定できるようにする

区間 \([l,r]\) に空き地点があるかは、

区間の長さ \(r-l+1\) が、その区間にある街灯の個数より大きいか

で判定できます。

つまり、

\((r-l+1) > \text{occupied count in } [l,r]\)

なら空き地点があります。

判定関数 feasible(D)

\(D\) を固定して、可能かどうかを調べます。

1. 悪い隙間を列挙する

\(G_i > D\) である隙間を集めます。

悪い隙間が \(3\) つ以上あれば不可能なので、すぐ False を返します。

2. 各街灯を「取り除く街灯」として試す

街灯 \(A_i\) を取り除くと仮定します。

このとき、取り除いた後に残る悪い隙間の数を数えます。

• 左の隙間 \(G_{i-1}\) は消える
• 右の隙間 \(G_i\) は消える
• 内部の街灯なら、新しい隙間 \(A_{i+1}-A_{i-1}\) ができる

取り除いた後の悪い隙間の個数を \(c\) とします。

3. \(c > 1\) の場合

街灯を置くことで直せる悪い隙間は高々 \(1\) つなので、不可能です。

4. \(c = 1\) の場合

残っている唯一の悪い隙間を、新しく置く街灯で分割できるかを調べます。

悪い隙間が \((u,v)\) なら、置ける位置は

\([\max(u+1, v-D), \min(v-1, u+D)]\)

です。

この区間に元々空いている地点があれば可能です。

5. \(c = 0\) の場合

取り除いた時点で、すべての隙間は \(D\) 以下です。

この場合は、どこかに街灯を置いても新しい隙間が \(D\) 以下になる場所があればよいです。

候補は次の通りです。

• 残った街灯のうち最も左の街灯より左
• 残った街灯のうち最も右の街灯より右
• 元々存在した、空き地点を含む隙間の中
• 取り除いた街灯の左右がつながってできた新しい隙間の中

それぞれについて、条件を満たす元々空いている地点があるかを累積和で調べます。

二分探索

feasible(D) が単調なので、\(D\) を二分探索します。

• feasible(D) == True なら、もっと小さい \(D\) を試す
• feasible(D) == False なら、もっと大きい \(D\) を試す

最終的に、可能な最小の \(D\) が答えです。

計算量

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

実装のポイント

• 移設先は「元々空いている地点」でなければなりません。取り除いた街灯の元の位置に戻すことはできないため、累積和で空き地点の有無を正確に判定します。

• 区間 \([l,r]\) に空きがあるかは、(r-l+1) > pref[r] - pref[l-1] で判定できます。

• 最大暗区間は街灯同士の隣接差だけを見るので、道路の端 \(1,N\) との距離は考えません。ただし、移設先は \(1\) 以上 \(N\) 以下である必要があります。

• 悪い隙間が \(3\) つ以上ある場合は即座に不可能とできます。これにより、判定内で扱う悪い隙間は高々 \(2\) つになります。

  ソースコード

import sys

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    N, M = data[0], data[1]
    A = sorted(data[2:])

    G = [A[i + 1] - A[i] for i in range(M - 1)]
    empty_gap_count = sum(1 for x in G if x >= 2)

    occ = bytearray(N + 1)
    for x in A:
        occ[x] = 1

    pref = [0] * (N + 1)
    s = 0
    for i in range(1, N + 1):
        s += occ[i]
        pref[i] = s

    def feasible(D):
        a = A
        g = G
        pref_local = pref
        m = M
        n = N
        m1 = m - 1
        egc = empty_gap_count

        bad_idxs = []
        for idx, val in enumerate(g):
            if val > D:
                if len(bad_idxs) == 2:
                    return False
                bad_idxs.append(idx)

        C = len(bad_idxs)

        bad_split = []
        for j in bad_idxs:
            u = a[j]
            v = a[j + 1]
            l = v - D
            t = u + 1
            if l < t:
                l = t
            r = u + D
            t = v - 1
            if r > t:
                r = t
            bad_split.append(l <= r and (r - l + 1) > (pref_local[r] - pref_local[l - 1]))

        for i in range(m):
            c = C

            if i > 0 and g[i - 1] > D:
                c -= 1
            if i < m1 and g[i] > D:
                c -= 1

            hbad = False
            if 0 < i < m1:
                if a[i + 1] - a[i - 1] > D:
                    c += 1
                    hbad = True

            if c > 1:
                continue

            if c == 0:
                if i == 0:
                    first = a[1]
                else:
                    first = a[0]

                l = first - D
                if l < 1:
                    l = 1
                r = first - 1
                if l <= r and (r - l + 1) > (pref_local[r] - pref_local[l - 1]):
                    return True

                if i == m1:
                    last = a[m - 2]
                else:
                    last = a[m1]

                l = last + 1
                r = last + D
                if r > n:
                    r = n
                if l <= r and (r - l + 1) > (pref_local[r] - pref_local[l - 1]):
                    return True

                cnt = egc
                if i > 0 and g[i - 1] >= 2:
                    cnt -= 1
                if i < m1 and g[i] >= 2:
                    cnt -= 1
                if cnt > 0:
                    return True

                if 0 < i < m1:
                    l = a[i - 1] + 1
                    r = a[i + 1] - 1
                    if l <= r and (r - l + 1) > (pref_local[r] - pref_local[l - 1]):
                        return True

            else:
                if hbad:
                    u = a[i - 1]
                    v = a[i + 1]
                    l = v - D
                    t = u + 1
                    if l < t:
                        l = t
                    r = u + D
                    t = v - 1
                    if r > t:
                        r = t
                    if l <= r and (r - l + 1) > (pref_local[r] - pref_local[l - 1]):
                        return True
                else:
                    left = i - 1
                    right = i
                    for k, j in enumerate(bad_idxs):
                        if j != left and j != right:
                            if bad_split[k]:
                                return True
                            break

        return False

    lo, hi = 0, N
    while hi - lo > 1:
        mid = (lo + hi) // 2
        if feasible(mid):
            hi = mid
        else:
            lo = mid

    print(hi)

if __name__ == "__main__":
    main()

---

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