概要

\(M\) 個の区間キャンペーンからちょうど \(K\) 個を選び、選ばれた区間の和集合に含まれる商品の利益合計を最大化する問題です。

\(K \leq 10\) と小さいことを利用し、「現在までに選んだキャンペーン数」と「右端の位置」を状態にした DP を行います。

考察

まず重要な点として、すべての利益 \(V_i\) は正です。

そのため、キャンペーンを追加で選んでも、売れる商品の集合は広がるか同じであり、利益が減ることはありません。

したがって、

「ちょうど \(K\) 個選ぶ最大値」 = 「高々 \(K\) 個選ぶ最大値」

として考えることができます。

もし \(K\) 個未満のキャンペーンで得られる利益が最大だったとしても、残りのキャンペーンを適当に追加すれば利益は減らず、ちょうど \(K\) 個にできます。

---

区間を左から右へ見ていくことを考えます。

すでにいくつかのキャンペーンを選んでいて、売れている商品のうち最も右の位置が \(x\) だとします。

新しくキャンペーン \([L, R]\) を選ぶとき、次の 2 通りがあります。

1. 以前の右端が区間の左より左にある場合

つまり \(x < L\) の場合です。

このとき、区間 \([L, R]\) はこれまで売れていた商品と重ならないので、新しく増える利益は

\[ S_R - S_{L-1} \]

です。

ここで \(S_i\) は利益の累積和です。

2. 以前の右端が区間の中にある場合

つまり \(L \leq x < R\) の場合です。

このとき、\(L\) から \(x\) まではすでに売れていると考えられるので、新しく増えるのは \(x+1\) から \(R\) までです。

増える利益は

\[ S_R - S_x \]

です。

---

素朴に、各キャンペーン \([L, R]\) に対してすべての \(x\) を試すと、最悪で \(O(KMN)\) になってしまい、\(N, M \leq 10^5\) では間に合いません。

そこで、以下の 2 種類の最大値を高速に求めます。

• \(x < L\) の最大値
  \(\max dp[x]\) を累積最大で求める
• \(L \leq x < R\) の最大値
  \(\max (dp[x] - S_x)\) をセグメント木で求める

アルゴリズム

累積和を

\[ S_i = V_1 + V_2 + \cdots + V_i \]

とします。

DP を次のように定義します。

\[ dp_t[r] \]

を、\(t\) 個の有効なキャンペーンを選んだとき、売れている商品の最も右の位置が \(r\) である場合の最大利益とします。

初期状態は

\[ dp_0[0] = 0 \]

です。

商品は \(1\) 番から \(N\) 番なので、位置 \(0\) は「まだ何も売れていない」ことを表します。

---

キャンペーン \([L, R]\) を最後に選ぶことを考えます。

前の右端を \(x\) とすると、遷移は次のようになります。

\(x < L\) の場合

新しく \([L, R]\) 全体が売れるので、

\[ dp_t[R] = \max \left( dp_t[R], dp_{t-1}[x] + S_R - S_{L-1} \right) \]

です。

このとき必要なのは

\[ \max_{0 \leq x \leq L-1} dp_{t-1}[x] \]

なので、累積最大 pref で \(O(1)\) で求めます。

---

\(L \leq x < R\) の場合

新しく売れるのは \(x+1\) から \(R\) なので、

\[ dp_t[R] = \max \left( dp_t[R], dp_{t-1}[x] + S_R - S_x \right) \]

です。

これは変形すると、

\[ dp_{t-1}[x] - S_x + S_R \]

です。

\(S_R\) はキャンペーン \([L, R]\) に対して固定なので、必要なのは

\[ \max_{L \leq x < R} (dp_{t-1}[x] - S_x) \]

です。

これはセグメント木で区間最大を取ることで \(O(\log N)\) で求めます。

---

各 \(t = 1, 2, \ldots, K\) について、すべてのキャンペーンを見て DP を更新します。

最終的な答えは、\(1\) 個以上 \(K\) 個以下のキャンペーンを選んだ場合の最大値です。

コードでは各段階の cur[i] の最大値で ans を更新しています。

計算量

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

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

実装のポイント

• 利益の合計は最大で \(10^5 \times 10^9 = 10^{14}\) 程度になるため、long long を使います。
• 到達不可能な DP 状態は非常に小さい値 NEG で管理します。
• 累積和は \(1\)-indexed にすると、区間 \([L, R]\) の利益を

$\( S_R - S_{L-1} \)$

と簡単に求められます。

• セグメント木には

$\( dp_{t-1}[i] - S_i \)$

を入れておき、区間 \([L, R)\) の最大値を取得します。 - 答えは「高々 \(K\) 個」の最大値として更新します。これは、利益がすべて正なので、ちょうど \(K\) 個選ぶ場合と同じ値になるためです。

ソースコード

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
const ll NEG = -(1LL << 62);

struct SegTree {
    int n;
    vector<ll> dat;

    void build(const vector<ll>& a) {
        int m = (int)a.size();
        n = 1;
        while (n < m) n <<= 1;
        dat.assign(2 * n, NEG);
        for (int i = 0; i < m; i++) dat[n + i] = a[i];
        for (int i = n - 1; i >= 1; i--) {
            dat[i] = max(dat[i << 1], dat[i << 1 | 1]);
        }
    }

    ll prod(int l, int r) {
        ll res = NEG;
        l += n;
        r += n;
        while (l < r) {
            if (l & 1) res = max(res, dat[l++]);
            if (r & 1) res = max(res, dat[--r]);
            l >>= 1;
            r >>= 1;
        }
        return res;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, M, K;
    cin >> N >> M >> K;

    vector<ll> S(N + 1, 0);
    for (int i = 1; i <= N; i++) {
        ll v;
        cin >> v;
        S[i] = S[i - 1] + v;
    }

    vector<pair<int, int>> intervals(M);
    for (int i = 0; i < M; i++) {
        cin >> intervals[i].first >> intervals[i].second;
    }

    vector<ll> prev(N + 1, NEG), cur(N + 1, NEG);
    vector<ll> pref(N + 1), arr(N + 1);
    prev[0] = 0;

    ll ans = 0;
    SegTree seg;

    for (int k = 1; k <= K; k++) {
        pref[0] = prev[0];
        for (int i = 1; i <= N; i++) {
            pref[i] = max(pref[i - 1], prev[i]);
        }

        for (int i = 0; i <= N; i++) {
            if (prev[i] <= NEG / 2) arr[i] = NEG;
            else arr[i] = prev[i] - S[i];
        }
        seg.build(arr);

        fill(cur.begin(), cur.end(), NEG);

        for (auto [L, R] : intervals) {
            ll best = NEG;

            if (pref[L - 1] > NEG / 2) {
                best = max(best, pref[L - 1] + S[R] - S[L - 1]);
            }

            if (L < R) {
                ll q = seg.prod(L, R);
                if (q > NEG / 2) {
                    best = max(best, q + S[R]);
                }
            }

            cur[R] = max(cur[R], best);
        }

        for (int i = 1; i <= N; i++) {
            ans = max(ans, cur[i]);
        }

        prev.swap(cur);
    }

    cout << ans << '\n';
    return 0;
}

---

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