概要

この問題は、与えられた \(M\) 個の区間（読書プラン）から、カバーする範囲（読んだ本の種類数）の合計が最大となるように、最大 \(K\) 個の区間を選択する問題です。

区間同士が重なり合う可能性があるため、単純な欲張り法では解けません。しかし、「区間の包含関係の除去」と「動的計画法（DP）」、さらに「スライド最大値」を組み合わせることで、制限時間内に高速に解くことができます。

---

考察

1. 包含関係にある区間の除去

まず、ある区間 \(A\) が別の区間 \(B\) に完全に含まれている場合（\(L_B \leq L_A\) かつ \(R_A \leq R_B\)）、区間 \(A\) を選ぶメリットはありません。なぜなら、区間 \(A\) を選ぶ代わりに区間 \(B\) を選んだ方が、消費するプラン数は同じ \(1\) のまま、より広い（または同等の）範囲をカバーできるからです。

したがって、他の区間に完全に含まれるような区間はあらかじめ除外して考えて差し支えありません。

包含関係を除去した後の区間を、左端 \(L_i\) の昇順にソートすると、右端 \(R_i\) も必ず厳密に単調増加します。 すなわち、任意の隣り合う区間 \(i, i+1\) について、以下の関係が成り立ちます。 $\(L_i < L_{i+1} \quad \text{かつ} \quad R_i < R_{i+1}\)$

これにより、区間の位置関係が「左から右へきれいに並ぶ」ようになり、動的計画法（DP）を適用しやすくなります。

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

\(K\) が最大 \(10\) と非常に小さいことに着目します。 包含除去後の区間数を \(M'\) とし、以下のDPを定義します。

• \(\text{dp}[i][j]\) ： \(i\) 番目の区間を最後に選び、これまでに合計 \(j\) 個の区間を選んだときの、カバーする長さの最大値

次に選ぶ区間を \(i\) としたとき、その直前に選んだ区間を \(p\) （\(0 \le p < i\)）とします。 区間 \(p\) と区間 \(i\) の重なり方によって、新たに増えるカバー範囲は以下の2パターンに分かれます。

パターンA：重なりがない場合（\(R_p < L_i\)）

区間 \(p\) と区間 \(i\) は完全に離れています。新しくカバーされる長さは、区間 \(i\) の長さそのもの（\(R_i - L_i + 1\)）です。 $\(\text{dp}[i][j] = \text{dp}[p][j-1] + (R_i - L_i + 1)\)$

パターンB：重なりがある場合（\(R_p \geq L_i\)）

包含関係は除去されているため、位置関係は \(L_p < L_i \leq R_p < R_i\) となります。 重なっている部分は \([L_i, R_p]\) なので、新しくカバーされる長さは、重なりを除いた右側の部分（\(R_i - R_p\)）です。 $\(\text{dp}[i][j] = \text{dp}[p][j-1] + (R_i - R_p)\)$

---

アルゴリズム

遷移の高速化

愚直にすべての \(p < i\) について遷移を試すと、DPの計算に \(O(M^2 K)\) かかり、 \(M = 10^5\) では実行時間制限に間に合いません。そこで、遷移を高速化します。

パターンAとパターンBの境界となるインデックスを \(\text{th}\) とします。これは \(R_p \geq L_i\) を満たす最小の \(p\) です。 \(i\) が増加するにつれて \(L_i\) も増加するため、この境界 \(\text{th}\) は右にしか移動しません（単調増加）。

1. \(p < \text{th}\) の範囲（パターンA：重なりなし）

この範囲では、 \(\text{dp}[p][j-1]\) の最大値に \(R_i - L_i + 1\) を足せばよいです。 \(\text{th}\) が右に進むたびに、それまでに通り過ぎた \(\text{dp}[p][j-1]\) の最大値を max_A として保持・更新していくことで、各ステップ \(O(1)\) で最大値を取得できます。

2. \(\text{th} \leq p < i\) の範囲（パターンB：重なりあり）

この範囲では、 \(\text{dp}[p][j-1] - R_p + R_i\) の最大値を求めたいです。 \(R_i\) は \(p\) に依存しないため、 \(\text{th} \leq p < i\) の範囲における \(\text{dp}[p][j-1] - R_p\) の最大値が分かればよいです。

\(i\) が \(1\) 増えるとき、この範囲（窓）の左端 \(\text{th}\) は右に移動し、右端 \(i-1\) も右に移動します。 これは「スライド窓（Sliding Window）」の形をしており、デック（deque）を用いたスライド最大値のアルゴリズム（Monotonic Queue）を使用することで、各ステップ \(O(1)\) で最大値を管理・取得できます。

実装における遷移式の共通化

コード中では、計算をスマートに共通化するために以下のように変形しています。 $\(\text{dp}[i][j] = \text{best} + (R_i - L_i + 1)\)$

• パターンAのとき： \(\text{best} = \text{dp}[p][j-1]\)
• パターンBのとき： \(\text{best} = \text{dp}[p][j-1] - R_p + L_i - 1\)

このように best を定義することで、どちらのパターンでも最終的に同じ式で \(\text{dp}[i][j]\) を更新できます。

---

計算量

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

  • 区間のソートと包含除去に \(O(M \log M)\) かかります。
  • DPの計算において、外側のループは \(K\) 回、内側のループは \(M'\) 回（\(M' \le M\)）回ります。内側のループ内では、デックへの要素の追加・削除や境界 \(\text{th}\) の進め方は、全体を通してアモルタイズ（ならし） \(O(1)\) で行われるため、DP全体の計算量は \(O(KM)\) となります。
  • \(M \le 10^5, K \le 10\) であるため、実行時間制限に余裕で間に合います。

• 空間計算量: \(O(KM)\)

  • DPテーブル \(\text{dp}[M'+1][K+1]\) を保持するために \(O(KM)\) のメモリを使用します。

---

実装のポイント

1. 包含関係の除去: 区間を \(L_i\) の昇順、 \(R_i\) の降順でソートします。この順に走査すると、これまでに現れた最大の右端を max_r としたとき、 \(R_i \le \text{max\_r}\) となる区間はすべて他の区間に含まれているため、簡単に除外できます。

2. スライド最大値のデック管理: デックには (インデックス, 値) のペアを格納します。新しく要素を追加する際は、デックの末尾にある自身より小さい値をすべて取り除くことで、デック内の値が常に降順（単調減少）になるように維持します。これにより、デックの先頭が常に現在の窓内での最大値になります。

   ソースコード

from collections import deque
import sys


def solve():
    input = sys.stdin.read
    data = input().split()
    if not data:
        return
    N = int(data[0])
    M = int(data[1])
    K = int(data[2])

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

    # 包含関係にある区間の除去
    # Lの昇順、Rの降順でソート
    intervals.sort(key=lambda x: (x[0], -x[1]))

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

    M_prime = len(filtered)
    K = min(K, M_prime)

    if K == 0:
        print(0)
        return

    # 1-based indexにするために先頭にダミーを挿入
    L = [0] * (M_prime + 1)
    R = [0] * (M_prime + 1)
    for i in range(M_prime):
        L[i + 1] = filtered[i][0]
        R[i + 1] = filtered[i][1]

    # dp[i][j] : i番目の区間を最後に選び、合計j個選んだときの最大カバー数
    INF = float("inf")
    dp = [[-INF] * (K + 1) for _ in range(M_prime + 1)]
    dp[0][0] = 0

    ans = 0

    for j in range(1, K + 1):
        max_A = dp[0][j - 1]
        th = 1
        deq = deque()

        for i in range(1, M_prime + 1):
            # 1. i-1 をスライド窓の右端として追加
            if i - 1 >= 1:
                val = dp[i - 1][j - 1] - R[i - 1]
                if val > -INF:
                    while deq and deq[-1][1] <= val:
                        deq.pop()
                    deq.append((i - 1, val))

            # 2. th を進める (R[th] < L[i] の間)
            while th < i and R[th] < L[i]:
                if dp[th][j - 1] > -INF:
                    max_A = max(max_A, dp[th][j - 1])
                if deq and deq[0][0] == th:
                    deq.popleft()
                th += 1

            # 3. dp[i][j] の計算
            best = -INF
            if max_A > -INF:
                best = max(best, max_A)
            if deq:
                best = max(best, deq[0][1] + L[i] - 1)

            if best > -INF:
                dp[i][j] = best + (R[i] - L[i] + 1)
                ans = max(ans, dp[i][j])

    print(ans)


if __name__ == "__main__":
    solve()

---

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