概要

最大 \(K\) 個の区間 \([L_i, R_i]\) を選び、その和集合の長さを最大化する問題です。
\(K \leq 10\) と小さい一方で \(M \leq 10^5\) と大きいため、区間 DP を高速化して解きます。

考察

まず、ある読書プランの区間が別の読書プランの区間に完全に含まれている場合を考えます。

例えば、

• プラン A: \([2, 10]\)
• プラン B: \([4, 7]\)

があるとき、プラン B を選ぶよりプラン A を選んだ方が読める本は必ず多いか同じです。
したがって、他の区間に完全に含まれる区間は選ぶ必要がありません。

区間を \(L\) 昇順、\(R\) 降順でソートし、左から見てこれまでの最大の \(R\) より大きい \(R\) を持つ区間だけ残すと、不要な区間を削除できます。

削除後の区間を

\[ [l_0, r_0], [l_1, r_1], \dots, [l_{m-1}, r_{m-1}] \]

とすると、次の性質があります。

• \(l_0 < l_1 < \dots < l_{m-1}\)
• \(r_0 < r_1 < \dots < r_{m-1}\)

つまり、左端も右端も単調増加します。

---

次に DP を考えます。

\(dp_t[i]\) を、

ちょうど \(t\) 個の区間を選び、最後に選ぶ区間が \(i\) 番目であるときの読める本の最大数

とします。

区間 \(j\) の次に区間 \(i\) を選ぶとします。
ただし \(j < i\) です。

このとき、区間の右端は単調増加しているので、追加で読める本の数は次のようになります。

1. 区間 \(j\) と区間 \(i\) が重ならない場合

\[ r_j < l_i \]

なら、区間 \(i\) はそれまで読んだ本と重ならないので、追加分は区間 \(i\) 全体です。

\[ r_i - l_i + 1 \]

2. 区間 \(j\) と区間 \(i\) が重なる場合

\[ r_j \geq l_i \]

なら、区間 \(i\) のうち \(r_j\) までの部分はすでに読んでいます。
新しく読めるのは \(r_j+1\) から \(r_i\) までなので、

\[ r_i - r_j \]

冊です。

したがって、素直に遷移を書くと

\[ dp_t[i] = \max_{j < i} \left( dp_{t-1}[j] + \text{追加分} \right) \]

となります。

しかし、これをそのまま計算すると \(O(KM^2)\) になり、\(M \leq 10^5\) では間に合いません。

---

そこで、各 \(i\) について

\[ p_i = r_j < l_i \text{ を満たす最大の } j \]

を求めます。

つまり、\(p_i\) 以前の区間は区間 \(i\) と重ならず、\(p_i+1\) 以降かつ \(i-1\) 以前の区間は区間 \(i\) と重なります。

遷移は次の 2 つに分けられます。

\[ dp_t[i] = \max \left( \max_{j \leq p_i} dp_{t-1}[j] + (r_i - l_i + 1), \max_{p_i < j < i} dp_{t-1}[j] + (r_i - r_j) \right) \]

後半は式変形して、

\[ dp_{t-1}[j] + (r_i - r_j) = (dp_{t-1}[j] - r_j) + r_i \]

となります。

つまり、

• 前半は \(dp_{t-1}\) の prefix max
• 後半は \(dp_{t-1}[j] - r_j\) の区間最大

を高速に求めればよいです。

後半の区間は \(i\) が増えるにつれてスライドしていくので、単調キューを使って \(O(1)\) 償却で最大値を取得できます。

アルゴリズム

1. 区間を \(L\) 昇順、\(R\) 降順でソートする。
2. 他の区間に含まれる区間を削除する。
   • これまで見た最大の \(R\) より大きい \(R\) を持つ区間だけ残す。
3. 残った区間数を \(m\) とする。
4. 各区間の長さ

$\( len_i = r_i - l_i + 1 \)$

を計算する。 5. \(K=1\) の場合は、最大の区間長を出力する。 6. 各 \(i\) について、\(p_i\) を尺取り法で求める。 - \(p_i\) は \(r_j < l_i\) を満たす最大の \(j\) 7. DP を行う。 - 初期状態：

 $$
 dp_1[i] = len_i
 $$

• \(t=2\) から \(K\) まで更新する。

• 遷移は

  $\( dp_t[i] = \max \left( \max_{j \leq p_i} dp_{t-1}[j] + len_i, \max_{p_i < j < i} (dp_{t-1}[j] - r_j) + r_i \right) \)$

• 1 つ目の最大値は prefix max で求める。

• 2 つ目の最大値は単調キューで求める。

1. 「最大 \(K\) 個」なので、\(1\) 個から \(K\) 個までの DP の最大値を答えにする。

計算量

• 時間計算量: \(O(M \log M + KM)\)
• 空間計算量: \(O(M)\)

\(K \leq 10\) なので、DP 部分は十分高速です。

実装のポイント

• 区間の長さは両端を含むので、

$\( r_i - l_i + 1 \)$

です。

• 含まれる区間を削除するときは、ソート順を

  intervals.sort(key=lambda x: (x[0], -x[1]))

とします。

同じ左端を持つ区間では右端が大きいものを先に見ることで、短い区間を正しく削除できます。

• \(p_i\) は、\(r_i\) が単調増加しているため、尺取り法で全体 \(O(M)\) で求められます。

• DP では不可能な状態を表すために、十分小さい値 NEG を使います。

• 「ちょうど \(K\) 個」ではなく「最大 \(K\) 個」なので、各 DP 層の最大値を答え候補として更新する必要があります。

  ソースコード

import sys

def main():
    data = sys.stdin.buffer.read().split()
    if not data:
        return

    M = int(data[1])
    K = int(data[2])

    intervals = []
    idx = 3
    for _ in range(M):
        l = int(data[idx])
        r = int(data[idx + 1])
        idx += 2
        intervals.append((l, r))

    intervals.sort(key=lambda x: (x[0], -x[1]))

    ls = []
    rs = []
    max_r = 0
    for l, r in intervals:
        if r > max_r:
            ls.append(l)
            rs.append(r)
            max_r = r

    m = len(ls)
    lens = [rs[i] - ls[i] + 1 for i in range(m)]

    ans = max(lens)
    if K == 1 or m == 1:
        print(ans)
        return

    p = [0] * m
    j = 0
    for i, l in enumerate(ls):
        while j < m and rs[j] < l:
            j += 1
        p[i] = j - 1

    kk = min(K, m)
    NEG = -10**30

    dp_prev = lens[:]
    q = [0] * m

    for _ in range(2, kk + 1):
        pref = [0] * m
        pm = NEG
        for i, v in enumerate(dp_prev):
            if v > pm:
                pm = v
            pref[i] = pm

        b = [dp_prev[i] - rs[i] for i in range(m)]
        cur = [NEG] * m

        head = 0
        tail = 0

        for i in range(m):
            add = i - 1
            if add >= 0:
                val = b[add]
                while tail > head and b[q[tail - 1]] <= val:
                    tail -= 1
                q[tail] = add
                tail += 1

            left = p[i] + 1
            while head < tail and q[head] < left:
                head += 1

            best = NEG
            pi = p[i]

            if pi >= 0:
                cand = pref[pi] + lens[i]
                if cand > best:
                    best = cand

            if head < tail:
                cand = b[q[head]] + rs[i]
                if cand > best:
                    best = cand

            cur[i] = best

        layer_max = max(cur)
        if layer_max > ans:
            ans = layer_max

        dp_prev = cur

    print(ans)

if __name__ == "__main__":
    main()

---

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