概要

イベント会場の数 \(N\) が小さいことを利用し、「影響を受けないように避けるイベント会場の集合」を全探索します。
各集合について、そのイベント会場たちに重ならない点検区間だけを使って間隔制約を満たせるかを判定します。

考察

まず、点検区間を \(0\) 個置く場合を考えます。
問題文より、\(T \leq M\) なら点検区間を置かなくても条件を満たせます。このとき影響を受けるイベント会場は \(0\) 個なので、答えは \(0\) です。

以降は \(T > M\) として、少なくとも \(1\) 個は点検区間を置く必要があります。

「影響を受ける数を最小化」から「避ける数を最大化」へ

あるイベント会場が点検区間と一度も重ならなければ、そのイベント会場は「避けられた」と考えます。

• 影響を受けるイベント会場数を最小化する
• 避けられるイベント会場数を最大化する

この 2 つは同じです。

\(N \leq 12\) なので、イベント会場の部分集合は高々 \(2^{12} = 4096\) 通りです。
そこで、「この集合のイベント会場をすべて避けられるか？」を全探索します。

固定した避けたい集合に対する判定

避けたいイベント会場の集合を avoid とします。

点検区間の開始位置 \(s\) は整数で、\(0 \leq s \leq T-K\) です。
この点検区間 \((s, s+K)\) がイベント会場 \((L_i, R_i)\) と重なる条件は、開区間同士の共通部分が空でないことなので、

\[ s < R_i \quad \text{かつ} \quad L_i < s+K \]

です。

したがって、各開始位置 \(s\) について「どのイベント会場と重なるか」をビット集合として前計算しておきます。

avoid に含まれるイベント会場と重ならない開始位置だけが使えます。

間隔制約の言い換え

点検区間の開始位置を昇順に

\[ s_1 \leq s_2 \leq \cdots \leq s_p \]

とします。

条件は以下です。

\[ s_1 \leq M \]

\[ s_{j+1} - (s_j + K) \leq M \]

\[ T - (s_p + K) \leq M \]

2 番目の条件は次のように変形できます。

\[ s_{j+1} - s_j \leq K + M \]

ここで

\[ D = K + M \]

とおきます。

また、最後の条件は

\[ s_p \geq T - K - M \]

です。ここで

\[ E = T - K - M \]

とおきます。

つまり、使える開始位置の中で、

• 最初の開始位置は \(M\) 以下
• 隣り合う開始位置の差は \(D = K+M\) 以下
• 最後の開始位置は \(E = T-K-M\) 以上

となる列を作れるかを判定すればよいです。

使える開始位置の連結成分

使える開始位置を小さい順に見ていきます。

隣り合う使える開始位置の差が \(D\) 以下なら、その 2 つは続けて使えます。
差が \(D\) より大きい場合、その間は飛び越えられないので別のグループになります。

したがって、使える開始位置を「差が \(D\) 以下でつながっている連結成分」に分けて考えます。

ある連結成分の中に、

• \(s \leq M\) となる開始位置
• \(s \geq E\) となる開始位置

の両方が存在すれば、その avoid は実現可能です。

アルゴリズム

1. 入力を受け取る。
2. もし \(T \leq M\) なら、点検区間を置かずに済むので 0 を出力して終了する。
3. 各開始位置 \(s\) について、点検区間 \((s, s+K)\) と重なるイベント会場の集合をビットマスクで前計算する。
4. 避けたいイベント会場の集合 avoid を全探索する。
5. 各 avoid について、以下を判定する。
   • overlapMask[s] & avoid == 0 なら、開始位置 \(s\) は使える。
   • 使える開始位置を小さい順に走査する。
   • 隣の使える開始位置との差が \(K+M\) を超えたら、新しい連結成分を開始する。
   • その連結成分に \(s \leq M\) の開始位置があるかを記録する。
   • 同じ連結成分内で \(s \geq T-K-M\) の開始位置も見つかれば、その avoid は実現可能。
6. 実現可能な avoid のうち、要素数が最大のものを求める。
7. 答えは

\[ N - \text{避けられるイベント会場数の最大値} \]

である。

計算量

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

\(T \leq 1000\), \(N \leq 12\) なので十分高速です。

実装のポイント

開区間同士が重なる条件は

\[ s < R_i \quad \text{かつ} \quad L_i < s+K \]

です。

端点で接しているだけの場合、例えば \((s, s+K)\) と \((s+K, R_i)\) は重なりません。
そのため、<= ではなく < を使う点に注意します。

また、最後の条件

\[ s_p \geq T-K-M \]

に対応する値 E は負になることがあります。
その場合、任意の開始位置 \(s \geq 0\) は自動的に最後の条件を満たします。コードではそのまま s >= E と判定すれば正しく処理できます。

ソースコード

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

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

    int T, N, K, M;
    cin >> T >> N >> K >> M;

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

    if (T <= M) {
        cout << 0 << '\n';
        return 0;
    }

    int maxS = T - K;
    vector<int> overlapMask(maxS + 1, 0);

    for (int s = 0; s <= maxS; s++) {
        int mask = 0;
        for (int i = 0; i < N; i++) {
            if (s < R[i] && L[i] < s + K) {
                mask |= (1 << i);
            }
        }
        overlapMask[s] = mask;
    }

    int bestAvoid = 0;
    int D = K + M;
    int E = T - K - M;

    for (int avoid = 0; avoid < (1 << N); avoid++) {
        int cnt = __builtin_popcount((unsigned)avoid);
        if (cnt <= bestAvoid) continue;

        bool feasible = false;
        bool inComponent = false;
        bool hasStart = false;
        int prev = -1;

        for (int s = 0; s <= maxS; s++) {
            if (overlapMask[s] & avoid) continue;

            if (!inComponent || s - prev > D) {
                inComponent = true;
                hasStart = false;
            }

            if (s <= M) hasStart = true;

            if (hasStart && s >= E) {
                feasible = true;
                break;
            }

            prev = s;
        }

        if (feasible) bestAvoid = cnt;
    }

    cout << N - bestAvoid << '\n';
    return 0;
}

---

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