概要

全長 \(T\) km の道路に長さ \(K\) の点検区間を「間隔制約」を満たすように配置し、いずれかの点検区間と重なるイベント会場の数を最小化する問題です。\(N \leq 12\) という小ささを利用し、「重なってもよい会場の集合」を全列挙して各々の実現可能性を貪欲法で判定します。

考察

重要な観察1：点検区間の開始位置と会場の重なり

点検区間 \((s, s+K)\) と会場 \((L_i, R_i)\) が重なる（開区間の共通部分が空でない）条件は

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

すなわち \(L_i - K < s < R_i\) です。\(s\) は整数なので

\[L_i - K + 1 \leq s \leq R_i - 1\]

となります。これにより、各開始位置 \(s\)（\(0 \leq s \leq T-K\)）について「その位置に置いた点検区間がどの会場と重なるか」をビットマスク overlapMask[s] として前計算できます。

重要な観察2：素朴なアプローチの問題点

点検区間の配置は個数も位置も自由で、組み合わせは膨大です。これを直接全探索することはできません。

そこで発想を変え、「どの会場を犠牲にする（重なりを許す）か」 という集合 \(H\) に着目します。\(N \leq 12\) なので、\(H\) は高々 \(2^{12} = 4096\) 通りしかありません。

各 \(H\) について「重なる会場を \(H\) の中だけに抑えながら、間隔制約を満たす配置が可能か？」を判定できれば、可能な \(H\) の中で最小の要素数が答えになります。

重要な観察3：実現可能性の貪欲判定

集合 \(H\) を固定すると、\(H\) に含まれない会場（=禁止集合 forb）に重なってしまう開始位置は使えません。つまり「使ってよい開始位置」は

\[\texttt{overlapMask}[s] \mathbin{\&} \texttt{forb} = 0\]

を満たす \(s\) だけです。

この許される位置のみを使って道路を「間隔制約」通りにカバーできるかを判定します。ここで、現在カバーできている右端を \(e\)（最初は \(0\)）とすると、

• \(T \leq e + M\) なら、これ以上点検区間を置かなくても終点までの制約を満たす → 成功
• そうでなければ、\(s \leq e + M\) かつ許される開始位置 \(s\) を選び、新しい右端を \(s + K\) に更新する

このとき、右端 \(e\) をできるだけ右に伸ばすほど後が楽になるので、許される範囲で最も右の開始位置を選ぶのが最適です（貪欲法）。\(s = e + M\) 以下で取れる最大の許可位置を選び続けます。進めなくなったら（位置が無い、または右端が伸びない）失敗です。

最も右の許可位置は、prevA[x] = x 以下で許される最大の開始位置 を前計算しておけば \(O(1)\) で取得できます。

アルゴリズム

1. 各開始位置 \(s\) について重なる会場のビットマスク overlapMask[s] を前計算する。
2. すべての部分集合 \(H\)（\(0 \leq H \leq 2^N - 1\)）を列挙する。
   • 禁止集合 forb = full ^ H を求める。
   • 各 \(s\) について「許される位置か」を判定し、prevA[s]（\(s\) 以下の最大許可位置）を計算する。
   • 右端 \(e=0\) から貪欲に点検区間を配置し、間隔制約を満たせるか判定する。
   • 満たせたら、\(H\) の要素数（popcount）で答えを更新する。
3. 最小値を出力する。

なお、\(p=0\)（点検区間を置かない）の場合は最初の T ≤ e + M（= T ≤ M）の判定でそのまま処理されます。

計算量

• 時間計算量: \(O(2^N \cdot T)\)
  • 各部分集合について prevA の計算が \(O(T)\)、貪欲ループも右端が毎回 \(K \geq 1\) 以上増えるので \(O(T)\) です。\(N \leq 12\), \(T \leq 1000\) より約 \(4 \times 10^6\) 回程度で十分高速です。
• 空間計算量: \(O(T)\)
  • overlapMask と prevA の配列に開始位置の個数分（最大 \(T+1\)）が必要です。

実装のポイント

• 重なり条件 \(L_i - K + 1 \leq s \leq R_i - 1\) の範囲は、開始位置の有効範囲 \([0, T-K]\) でクリップして適用します（lo=max(0,L-K+1), hi=min(maxS,R-1)）。

• 貪欲ループでは無限ループ防止のため、新しい右端 ne = s + K が現在の e より大きくならない（進まない）場合は失敗として打ち切ります。

• 終了条件 T <= e + M を最初にチェックすることで、点検区間が不要なケースも自然に扱えます。

• \(e + M\) が maxS を超えうるため、min(maxS, e+M) でクリップしてから prevA を参照します。

  ソースコード

#include <bits/stdc++.h>
using namespace std;
int main(){
    int T,N,K,M;
    scanf("%d %d %d %d",&T,&N,&K,&M);
    vector<int> L(N),R(N);
    for(int i=0;i<N;i++) scanf("%d %d",&L[i],&R[i]);
    int maxS=T-K; // start range 0..maxS
    vector<int> overlapMask(maxS+1,0);
    for(int i=0;i<N;i++){
        // event open (L,R) overlaps interval start s iff L-K < s < R
        int lo=max(0,L[i]-K+1), hi=min(maxS,R[i]-1);
        for(int s=lo;s<=hi;s++) overlapMask[s]|=(1<<i);
    }
    int full=(1<<N)-1;
    int ans=N+1;
    vector<int> prevA(maxS+1);
    for(int H=0;H<=full;H++){
        int forb=full^H;
        int last=-1;
        for(int s=0;s<=maxS;s++){
            if((overlapMask[s]&forb)==0) last=s; // start allowed (overlaps only events in H)
            prevA[s]=last;
        }
        long long e=0; bool feasible=false;
        while(true){
            if(T<=e+M){feasible=true;break;}
            long long limL=min((long long)maxS,e+M);
            int lim=(int)limL;
            int s=prevA[lim];
            if(s<0)break;
            long long ne=(long long)s+K;
            if(ne<=e)break;
            e=ne;
        }
        if(feasible) ans=min(ans,__builtin_popcount((unsigned)H));
    }
    printf("%d\n",ans);
    return 0;
}

---

この解説は claude4.8opus-high によって生成されました。