概要

本問題は、与えられた \(M\) 個の区間（読書プラン）から最大 \(K\) 個を選択し、それらの和集合の大きさ（カバーされる本の総数）を最大化する問題です。

区間同士の重複を考慮しながら、動的計画法（DP）とセグメント木を組み合わせることで、制限時間内に高速に解くことができます。

---

考察

1. 不要な区間の排除（フィルタリング）

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

したがって、以下の手順で不要な区間を排除します。 1. すべての区間を「左端 \(L_i\) の昇順（同じなら右端 \(R_i\) の降順）」でソートします。 2. 左から順に走査し、「これまでに現れたどの右端よりも、右端が右にある区間」のみを探索対象として残します。

このフィルタリングを行うと、残った区間（数を \(M'\) とします）は以下の性質を満たすようになります。 - 左端が単調増加する： \(L_1 < L_2 < \dots < L_{M'}\) - 右端も単調増加する： \(R_1 < R_2 < \dots < R_{M'}\)

これにより、区間同士の位置関係が非常にシンプルになります。

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

以下のようなDPテーブルを定義します。 - \(dp[j][i]\) : \(j\) 個の区間を選択し、最後に選んだ区間が（フィルタリング後の） \(i\) 番目の区間であるときの、カバーできる本の最大数。

\(j\) 個目の区間として \(i\) 番目の区間（\([L_i, R_i]\)）を選ぶとき、その直前に選んだ \((j-1)\) 個目の区間を \(p\) (\(p < i\)) とします。このとき、区間 \(p\) と区間 \(i\) の位置関係によって、新しく増える本の数は次の2パターンに分かれます。

パターンA：区間 \(p\) と区間 \(i\) が重ならない場合（\(R_p < L_i\)）

区間が重ならないため、単純に区間 \(i\) の長さがそのまま加算されます。 $\(\text{遷移後の値} = dp[j-1][p] + (R_i - L_i + 1)\)\( このパターンの最大値は、条件 \)R_p < L_i\( を満たす \)p\( の中での \)dp[j-1][p]\( の最大値に \)(R_i - L_i + 1)$ を足したものです。

パターンB：区間 \(p\) と区間 \(i\) が重なる場合（\(R_p \ge L_i\)）

フィルタリングの性質上、区間 \(p\) は区間 \(i\) に完全には含まれません（\(L_p < L_i\) かつ \(R_p < R_i\)）。 したがって、重なりを除いて新しくカバーされる部分は \([R_p + 1, R_i]\) となり、増える本の数は \(R_i - R_p\) となります。 $\(\text{遷移後の値} = dp[j-1][p] + (R_i - R_p) = (dp[j-1][p] - R_p) + R_i\)\( このパターンの最大値は、条件 \)R_p \ge L_i\( を満たす \)p\( の中での \)(dp[j-1][p] - R_p)\( の最大値に \)R_i$ を足したものです。

---

アルゴリズム

各 \(j\) (\(2 \le j \le K\)) について、DPテーブルの \(j-1\) 行目の値から \(j\) 行目の値を高速に計算します。

1. 境界の探索: \(R_p < L_i\) を満たす最大のインデックス \(p\) （これを p_max とする）を二分探索（lower_bound）で求めます。これにより、遷移元 \(p\) は以下のように分類されます。

   • \(p \le \text{p\_max}\) のとき：パターンA（重なりなし）
   • \(\text{p\_max} < p < i\) のとき：パターンB（重なりあり）

2. パターンAの高速化: \(p \le \text{p\_max}\) における \(dp[j-1][p]\) の最大値は、事前に累積最大値（プレフィックス・マックス）を計算しておくことで \(O(1)\) で取得できます。

3. パターンBの高速化: \(\text{p\_max} < p < i\) における \(dp[j-1][p] - R_p\) の最大値を求めるため、セグメント木を使用します。 あらかじめ配列 \(A[p] = dp[j-1][p] - R_p\) を乗せたセグメント木を構築しておくことで、任意の区間 \([\text{p\_max} + 1, i - 1]\) の最大値を \(O(\log M)\) で取得できます。

これらを組み合わせることで、各状態 \(dp[j][i]\) を \(O(\log M)\) で遷移させることができます。

---

計算量

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

  • 区間のソートとフィルタリングに \(O(M \log M)\) かかります。
  • DPの更新は、外側のループが \(K\) 回、内側のループが \(M'\) 回（\(M' \le M\)）回り、各ステップで二分探索とセグメント木のクエリを \(O(\log M)\) で行うため、全体で \(O(K M \log M)\) となります。\(K \le 10\) であるため、実行時間制限に十分間に合います。

• 空間計算量: \(O(K M)\) または \(O(M)\)

  • DPテーブルの保持に必要な空間は \(O(K M)\) です。直前の行のみを保持するようにすれば \(O(M)\) に削減することも可能です。

---

実装のポイント

• セグメント木の初期化: 到達不可能なDPの状態（値が極端に小さい負の数、コード中では -4e18）から遷移するのを防ぐため、セグメント木の初期値や単位元（e()）は十分に小さな負の値に設定します。

• \(K\) の上限: プランの総数 \(M'\) が \(K\) より小さくなる場合があるため、事前に \(K = \min(K, M')\) と更新しておくことで、余計な探索を防ぐことができます。

  ソースコード

#include <iostream>
#include <vector>
#include <algorithm>
#include <atcoder/segtree>

using namespace std;

long long op(long long a, long long b) {
    return max(a, b);
}

long long e() {
    return -4e18;
}

struct Interval {
    long long L, R;
    bool operator<(const Interval& other) const {
        if (L != other.L) return L < other.L;
        return R > other.R;
    }
};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    long long N;
    int M, K;
    if (!(cin >> N >> M >> K)) return 0;

    vector<Interval> intervals(M);
    for (int i = 0; i < M; ++i) {
        cin >> intervals[i].L >> intervals[i].R;
    }

    sort(intervals.begin(), intervals.end());

    vector<Interval> filtered;
    long long max_R = -1;
    for (const auto& interval : intervals) {
        if (interval.R > max_R) {
            filtered.push_back(interval);
            max_R = interval.R;
        }
    }

    int M_prime = filtered.size();
    K = min(K, M_prime);

    if (M_prime == 0) {
        cout << 0 << "\n";
        return 0;
    }

    vector<long long> R_vals(M_prime);
    for (int i = 0; i < M_prime; ++i) {
        R_vals[i] = filtered[i].R;
    }

    vector<vector<long long>> dp(K + 1, vector<long long>(M_prime, -4e18));

    for (int i = 0; i < M_prime; ++i) {
        dp[1][i] = filtered[i].R - filtered[i].L + 1;
    }

    long long ans = 0;
    for (int i = 0; i < M_prime; ++i) {
        ans = max(ans, dp[1][i]);
    }

    for (int j = 2; j <= K; ++j) {
        vector<long long> max_dp(M_prime);
        max_dp[0] = dp[j-1][0];
        for (int i = 1; i < M_prime; ++i) {
            max_dp[i] = max(max_dp[i-1], dp[j-1][i]);
        }

        vector<long long> seg_init(M_prime);
        for (int i = 0; i < M_prime; ++i) {
            if (dp[j-1][i] < -2e18) {
                seg_init[i] = -4e18;
            } else {
                seg_init[i] = dp[j-1][i] - filtered[i].R;
            }
        }
        atcoder::segtree<long long, op, e> seg(seg_init);

        for (int i = 0; i < M_prime; ++i) {
            long long L_i = filtered[i].L;
            long long R_i = filtered[i].R;

            auto it = lower_bound(R_vals.begin(), R_vals.end(), L_i);
            int p_max = distance(R_vals.begin(), it) - 1;

            long long val1 = -4e18;
            if (p_max >= 0) {
                val1 = max_dp[p_max];
            }

            long long val2 = -4e18;
            int start = p_max + 1;
            int end = i;
            if (start < end) {
                long long res = seg.prod(start, end);
                if (res > -2e18) {
                    val2 = res + L_i - 1;
                }
            }

            long long best_prev = max(val1, val2);
            if (best_prev > -2e18) {
                dp[j][i] = best_prev + (R_i - L_i + 1);
            }
            ans = max(ans, dp[j][i]);
        }
    }

    cout << ans << "\n";

    return 0;
}

---

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