概要

この問題は、全長 \(T\) km の高速道路に点検区間をいくつか設置し、間隔制約を満たしつつ、点検区間と重なるイベント会場の数を最小化する問題です。

イベント会場の数 \(N\) が最大で \(12\) と非常に小さいことに着目し、すでに重なったイベント会場の集合をビットで表すビットDP（動的計画法）を用いて解くことができます。

---

考察

1. イベント会場の数が小さいことに注目する

イベント会場の数 \(N\) は \(0 \le N \le 12\) と非常に小さいです。このように「選択した要素の集合」の全探索が \(2^N\) 通り（\(2^{12} = 4096\) 通り）に収まる場合、ビットDP（状態圧縮DP）が強力なアプローチになります。

2. 間隔制約の整理と「仮想的な開始地点」の導入

点検区間の開始地点を \(s_1 \le s_2 \le \cdots \le s_p\) としたとき、間隔制約は以下の通りです。 1. \(s_1 \le M\) 2. \(s_{j+1} - s_j \le M + K\) （\(1 \le j \le p-1\)） 3. \(T - s_p \le M + K\)

ここで、仮想的な \(0\) 番目の点検区間の開始地点を \(s_0 = -K\) と定義してみます。 すると、1番目の制約は以下のように変形できます。 $\(s_1 - s_0 = s_1 - (-K) \le M + K \iff s_1 \le M\)$

これにより、1番目の制約（起点からの距離）を、2番目の制約（点検区間同士の距離）と同じ形式 \(s_{j+1} - s_j \le M + K\) に統一して扱うことができます。

同様に、終端条件（最後の点検区間から終点まで）は以下のように表せます。 $\(s_p \ge T - K - M\)$

3. DP（動的計画法）の設計

点検区間の開始地点としてあり得る位置 \(s\) を \(0\) から \(T-K\) まで順に走査し、各 \(s\) を「採用するか・しないか」を決定していくDPを考えます。

状態として「重なったイベント会場の集合（ビットマスク）」を持たせますが、遷移（間隔制約の判定）を行うためには、最後に配置した点検区間の開始地点の情報が必要です。 次に配置できる点検区間の開始地点 \(s_{\text{next}}\) は、最後に配置した位置 \(s_{\text{last}}\) に対して \(s_{\text{next}} - s_{\text{last}} \le M + K \iff s_{\text{last}} \ge s_{\text{next}} - M - K\) を満たす必要があります。

したがって、同じイベントの被り状況（ビットマスク）であれば、最後に配置した位置 \(s_{\text{last}}\) は大きければ大きいほど、今後の選択肢が広がり有利になります。

これより、以下のDPテーブルを定義します。 - \(\text{dp}[\text{bit}]\) : 重なったイベント会場の集合が \(\text{bit}\) であるとき、最後に配置した点検区間の開始地点の最大値（不可能な場合は \(-\infty\)）

---

アルゴリズム

ステップ 1: 特例処理

\(T \le M\) の場合、点検区間を \(0\) 個（\(p=0\)）にすることが許されます。このときイベント会場との重複は \(0\) にできるため、即座に 0 を出力して終了します。

ステップ 2: イベント重複マスクの前計算

各 \(s \in [0, T-K]\) について、点検区間 \((s, s+K)\) を設置したときに重なるイベント会場の集合をビットマスク mask[s] として前計算しておきます。 点検区間 \((s, s+K)\) とイベント \((L_i, R_i)\) が重なる条件は、\(s < R_i\) かつ \(L_i < s+K\) です。

ステップ 3: DPテーブルの初期化

DPテーブルのサイズは \(2^N\) です。 - 仮想的な初期位置 \(s_0 = -K\) にのみ到達可能であるため、\(\text{dp}[0] = -K\) とします。 - それ以外の状態は \(-\infty\)（到達不可能）で初期化します。

ステップ 4: DPの遷移

\(s\) を \(0\) から \(T-K\) まで順にループします。

各 \(s\) について、現在のDPテーブルをコピーした配列 nxt を用意し、以下のように遷移を行います。 各状態 \(\text{bit}\) について、\(\text{dp}[\text{bit}] \ge s - M - K\) を満たす（＝直前の点検区間から \(s\) まで間隔制約を満たして到達できる）場合、点検区間 \(s\) を新たに配置できます。 $\(\text{nxt}[\text{bit} \mid \text{mask}[s]] = \max(\text{nxt}[\text{bit} \mid \text{mask}[s]], s)\)$

※ \(s\) を選ばない場合は状態は変化しないため、あらかじめ nxt を dp の内容で初期化しておくことで対応します。

ステップ 5: 答えの集計

すべての \(s\) の走査が終了した後、終端条件を満たす状態から答えを探します。 \(\text{dp}[\text{bit}] \ge T - K - M\) を満たすすべての \(\text{bit}\) のうち、立っているビット数（popcount）が最小のものが答えとなります。

---

計算量

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

• マスクの前計算: \(O(T \cdot N)\)
• DPの遷移: 外側のループが \(T - K + 1 \le T\) 回、内側のループが \(2^N\) 回です。よって全体で \(O(T \cdot 2^N)\) となります。
• \(T \le 1000, N \le 12\) のとき、最悪でも \(1000 \times 4096 \approx 4 \times 10^6\) 回程度の演算であり、実行時間制限に余裕で間に合います。

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

• mask 配列のサイズが \(T - K + 1\)、DPテーブルのサイズが \(2^N\) です。
• メモリ使用量は数メガバイト程度に収まり、非常に軽量です。

---

実装のポイント

• インプレース更新の回避: 同じ \(s\) を 1 回の遷移で複数回選んでしまう（同じ場所に何重にも重ねて置いてしまう）のを防ぐため、遷移元となる curr 配列と、遷移先となる nxt 配列を分けて管理しています。

• popcountの高速化: 最後の集計で各ビットマスクの立っているビット数を数える際、あらかじめ \(0\) から \(2^N-1\) までの popcount をテーブル化しておくことで、定数倍の高速化を図っています。

  ソースコード

import sys

def solve():
    input = sys.stdin.read
    data = input().split()
    if not data:
        return
    T = int(data[0])
    N = int(data[1])
    K = int(data[2])
    M = int(data[3])
    
    L = []
    R = []
    idx = 4
    for _ in range(N):
        L.append(int(data[idx]))
        R.append(int(data[idx+1]))
        idx += 2
        
    if T <= M:
        print(0)
        return

    # 各 s における点検区間 (s, s+K) と重なるイベント会場のビットマスクを前計算
    mask = [0] * (T - K + 1)
    for s in range(T - K + 1):
        m = 0
        for i in range(N):
            if s < R[i] and L[i] < s + K:
                m |= (1 << i)
        mask[s] = m

    num_states = 1 << N
    INF = 10**9
    dp0 = [-INF] * num_states
    dp1 = [-INF] * num_states
    
    # 初期状態: 起点 (位置 -K) に bit 0 が到達可能
    dp0[0] = -K

    curr = dp0
    nxt = dp1

    for s in range(T - K + 1):
        mask_s = mask[s]
        limit = s - M - K
        nxt[:] = curr
        for bit in range(num_states):
            val = curr[bit]
            if val >= limit:
                nbit = bit | mask_s
                if s > nxt[nbit]:
                    nxt[nbit] = s
        curr, nxt = nxt, curr

    popcount = [bin(i).count('1') for i in range(num_states)]
    ans = N
    limit_end = T - K - M
    for bit in range(num_states):
        if curr[bit] >= limit_end:
            if popcount[bit] < ans:
                ans = popcount[bit]
    print(ans)

if __name__ == '__main__':
    solve()

---

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