概要

この問題は、全長 \(T\) km の道路にいくつかの点検区間（長さ \(K\)）を適切に配置し、間隔制約を満たしつつ、与えられた \(N\) 個のイベント会場（開区間）と重なる点検区間の数を最小化する問題です。

イベント会場の数 \(N\) が最大でも \(12\) と非常に小さいことに着目し、ビット全探索（\(2^N\) 通り）と動的計画法（DP）を組み合わせることで、制限時間内に効率よく正解を求めることができます。

---

考察

1. イベント会場と点検区間の「重なり」の条件

ある点検区間の開始地点を \(s\) としたとき、この点検区間は開区間 \((s, s+K)\) と表されます。 これが \(i\) 番目のイベント会場 \((L_i, R_i)\) と重なる（共通部分を持つ）条件を考えます。

2つの開区間が重なる条件は、以下の不等式が同時に成り立つことです。 $\(s < R_i \quad \text{かつ} \quad L_i < s + K\)$

これを \(s\) について整理すると、次のようになります。 $\(L_i - K < s < R_i\)$

\(s\) は整数なので、この条件は以下と同値です。 $\(L_i - K + 1 \leq s \leq R_i - 1\)$

つまり、開始地点 \(s\) がこの範囲内にある点検区間を設置すると、イベント会場 \(i\) と重なってしまいます。

2. \(N \leq 12\) という制約の活用

イベント会場の数 \(N\) が非常に小さいため、「どのイベント会場を避ける（重ならないようにする）か」の組み合わせを全探索できます。 避けるイベント会場の集合をビット列（mask）で表すと、組み合わせは \(2^N = 2^{12} = 4096\) 通りしかありません。

避けるイベント会場の数を \(d\)（mask の立っているビット数）とすると、重なるイベント会場の数は \(N - d\) となります。 重なりを最小化したいので、避ける数 \(d\) が大きい順（\(N\) から \(0\) まで）に mask を探索し、その mask に含まれるすべてのイベント会場を避けつつ、間隔制約を満たす点検区間の配置が存在するかどうかを判定すればよいです。

3. 間隔制約を満たす配置の判定（DP）

特定の mask（避けるべきイベント会場の集合）が与えられたとき、それらと重ならないように点検区間を配置できるかを判定します。

まず、避けるべきイベント会場 \(i\) に対して、開始地点の禁止エリア \([L_i - K + 1, R_i - 1]\) を設定します。これにより、各 \(s \in [0, T-K]\) について「配置可能か（allowed[s]）」が決まります。

次に、間隔制約を満たすように点検区間の開始地点 \(s_1 < s_2 < \dots < s_p\) を選べるかを動的計画法（DP）で判定します。

• \(dp[x]\): 開始地点 \(x\) に点検区間を配置するような、間隔制約を満たす有効な配置が存在するかどうか（true / false）

初期化

最初の点検区間の開始地点 \(s_1\) は \(s_1 \leq M\) を満たす必要があります。 したがって、 \(0 \leq x \leq \min(T-K, M)\) かつ allowed[x] が真である \(x\) について、 \(dp[x] = \text{true}\) とします。

遷移

隣り合う点検区間の開始地点の間隔は \(s_{j+1} - s_j \leq K + M\) を満たす必要があります。 したがって、すでに \(dp[y] = \text{true}\) となる \(y\) が存在し、 \(x - y \leq K + M\) かつ allowed[x] が真であれば、 \(dp[x] = \text{true}\) と更新できます。

これを愚直に行うと \(O(T^2)\) かかりますが、「直前に true と判定されたインデックス last_true」を保持しておくことで、 \(x\) を左から右へ走査しながら \(O(T)\) で更新できます。

ゴール判定

最後の点検区間の開始地点 \(s_p\) は \(T - (s_p + K) \leq M \iff s_p \geq T - K - M\) を満たす必要があります。 DP終了後、 \(T - K - M \leq y \leq T - K\) の範囲に \(dp[y] = \text{true}\) となる \(y\) が1つでも存在すれば、条件を満たす配置が存在すると判定できます。

---

アルゴリズム

1. コーナーケースの処理: \(T \leq M\) の場合、点検区間を \(0\) 個設置すればよい（このとき重なりは \(0\)）ため、即座に 0 を出力して終了します。
2. 探索順序の準備: \(2^N\) 通りの mask を、立っているビット数（popcount）の降順にグループ分けします。
3. ビット全探索とDP: 避ける会場の数 \(d = N, N-1, \dots, 0\) の順に、該当する mask について以下の判定（solve(mask)）を行います。
   • mask で指定されたイベント会場と重なる開始地点 \(s\) を禁止する。
   • DPテーブルを初期化し、 \(O(T)\) の遷移で各地点に配置可能かを求める。
   • ゴール条件を満たす配置が存在すれば、その時点で探索を打ち切り、 \(N - d\) を出力して終了する。

---

計算量

時間計算量: \(O(2^N \cdot (N + T))\)

• mask の数は \(2^N\) 通り。
• 各 mask に対する判定処理（solve）において：
  • 禁止区間の設定: 避けるイベント会場の数を \(d\) とすると、各会場について禁止区間を塗りつぶすのに \(O(d \cdot T)\)。
  • DPテーブルの更新およびゴール判定: \(O(T)\)。
• 最悪の場合でも全体のステップ数は \(2^{12} \times 12 \times 1000 \approx 4.9 \times 10^7\) 回の単純なループ処理となり、実行時間制限に対して十分に高速（数ミリ秒〜数十ミリ秒で動作）です。

空間計算量: \(O(2^N + T)\)

• masks_by_pop に \(2^N\) 個の要素を格納します。
• DPテーブルや allowed 配列のサイズは \(O(T)\) です。
• メモリ使用量は数メガバイト程度であり、空間的にも非常に余裕があります。

---

実装のポイント

• 開区間の境界値の処理: 点検区間とイベント会場の重なりを避けるための禁止区間 \(L_i - K + 1 \leq s \leq R_i - 1\) のインデックスが、道路の範囲 \([0, T-K]\) をはみ出さないように max(0, ...) や min(max_s, ...) で適切にクリップしています。

• DPの高速化: last_true を用いた \(O(1)\) 遷移により、内側のDPループを極めて高速に処理しています。

• 早期終了による最適化: 避けるイベント会場の数 \(d\) が大きい順（重なる数が小さい順）に探索しているため、条件を満たす配置が最初に見つかった時点でそれがグローバルな最適解となり、即座にプログラムを終了できます。

  ソースコード

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

using namespace std;

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

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

    vector<int> L(N), R(N);
    for (int i = 0; i < N; ++i) {
        cin >> L[i] >> R[i];
    }

    // p = 0 の場合、点検区間を 0 個設置して T <= M を満たせば重なりは 0
    if (T <= M) {
        cout << 0 << "\n";
        return 0;
    }

    // p >= 1 の場合
    int max_s = T - K;
    vector<bool> allowed(max_s + 1);
    vector<bool> dp(max_s + 1);

    // mask で指定されたイベント会場と重ならないように配置できるか判定
    auto solve = [&](int mask) -> bool {
        fill(allowed.begin(), allowed.end(), true);
        for (int i = 0; i < N; ++i) {
            if ((mask >> i) & 1) {
                // 開区間 (L_i - K, R_i) に含まれる整数 s を禁止する
                int left = max(0, L[i] - K + 1);
                int right = min(max_s, R[i] - 1);
                for (int x = left; x <= right; ++x) {
                    allowed[x] = false;
                }
            }
        }

        fill(dp.begin(), dp.end(), false);
        // 初期化: s_1 <= M かつ s_1 は許容領域内
        for (int x = 0; x <= min(max_s, M); ++x) {
            if (allowed[x]) {
                dp[x] = true;
            }
        }

        int last_true = -1;
        for (int x = 0; x <= max_s; ++x) {
            if (dp[x]) {
                last_true = x;
            } else if (allowed[x]) {
                if (last_true != -1 && x - last_true <= K + M) {
                    dp[x] = true;
                    last_true = x;
                }
            }
        }

        // ゴール判定: T - (s_p + K) <= M  <=>  s_p >= T - K - M
        for (int y = max(0, max_s - M); y <= max_s; ++y) {
            if (dp[y]) {
                return true;
            }
        }
        return false;
    };

    // 重ならないイベント会場の数を最大化するため、popcount の降順に探索
    vector<vector<int>> masks_by_pop(N + 1);
    for (int mask = 0; mask < (1 << N); ++mask) {
        int pop = __builtin_popcount(mask);
        masks_by_pop[pop].push_back(mask);
    }

    for (int d = N; d >= 0; --d) {
        for (int mask : masks_by_pop[d]) {
            if (solve(mask)) {
                cout << N - d << "\n";
                return 0;
            }
        }
    }

    return 0;
}

---

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