概要

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

キャンペーンの区間を左端の昇順にソートし、セグメント木を用いた動的計画法（DP）を適用することで、重複する利益を正しく処理しながら高速に解を求めることができます。

考察

1. 素朴なアプローチとその限界

\(M\) 個のキャンペーンから \(K\) 個を選ぶ組み合わせは \(\binom{M}{K}\) 通りあります。制約 \(M \le 10^5, K \le 10\) では、組み合わせの数が最大で \(\binom{10^5}{10} \approx 2.7 \times 10^{43}\) 通りとなり、愚直な全探索は不可能です。

また、選んだ区間同士が重なっている場合、重複した部分の利益を \(1\) 回だけカウントするという処理を高速に行う必要があります。

2. 区間のソートとDPの設計

重複を効率的に処理するために、すべてのキャンペーンを左端 \(L_j\) の昇順にソートして、左から順番に採用するかどうかを決めていくDPを考えます。

商品の利益の累積和を \(S\) とします（\(S[i] = \sum_{k=1}^i V_k\)）。区間 \([L, R]\) の利益の総和は \(S[R] - S[L-1]\) と表せます。

区間を左端の昇順にソートして処理すると、新しく追加する区間 \([L, R]\) と、それまでに最後に選んだ区間（右端を \(x\) とします）との関係性は、以下の3つのパターンに整理できます。

パターン1：重なりがない場合（\(x < L\)）

新しく選ぶ区間 \([L, R]\) は、これまでに選んだどの区間とも重なりがありません。 新たに得られる利益は \(S[R] - S[L-1]\) です。

パターン2：一部が重なる場合（\(L \le x < R\)）

最後に選んだ区間の右端 \(x\) が、新しい区間の左端 \(L\) 以上、右端 \(R\) 未満にあります。 重複部分 \([L, x]\) はすでに回収されているため、新たに得られる利益は \([x+1, R]\) の部分、すなわち \(S[R] - S[x]\) となります。

パターン3：完全に含まれる場合（\(x \ge R\)）

新しい区間 \([L, R]\) は、すでに選んだ区間に完全に含まれています（ソートしているため、左端 \(L_{prev} \le L\) かつ \(R \le x\) となるため）。 この区間を選んでも利益は一切増えず、選べるキャンペーンの枠 \(K\) を無駄に消費するだけなので、この遷移は無視して構いません。

---

3. DPの定義と高速化

以上の考察から、以下のDPテーブルを定義します。

• \(dp[j][x]\) : これまでに \(j\) 個のキャンペーンを選び、最後に選んだキャンペーンの右端が \(x\) であるときの最大利益。

新しくキャンペーン \([L, R]\) を \(j\) 個目のキャンペーンとして追加するときの遷移式は、パターンの最大値をとることで次のようになります。

\[ dp[j][R] = S[R] + \max \left( \max_{0 \le x < L} (dp[j-1][x]) - S[L-1], \max_{L \le x < R} (dp[j-1][x] - S[x]) \right) \]

この遷移を愚直に計算すると、各キャンペーンに対して \(O(N)\) かかり、全体で \(O(M \cdot N)\) となって実行時間制限に間に合いません。 しかし、遷移式をよく見ると、以下の2つのセグメント木（RMQ: 区間最大値クエリ）を用意することで、それぞれ \(O(\log N)\) で遷移先を求められます。

1. セグメント木 \(T[j]\): \(T[j][x] = dp[j][x]\) を管理する。
   • パターン1の \(\max_{0 \le x < L} T[j-1][x]\) を \(O(\log N)\) で取得可能。
2. セグメント木 \(U[j]\): \(U[j][x] = dp[j][x] - S[x]\) を管理する。
   • パターン2の \(\max_{L \le x < R} U[j-1][x]\) を \(O(\log N)\) で取得可能。

アルゴリズム

1. 前処理:
   • 商品の利益の累積和 \(S\) を計算します。
   • キャンペーンの区間 \([L_j, R_j]\) を左端 \(L_j\) の昇順にソートします。
2. 初期化:
   • \(K+1\) 個のセグメント木 \(T[j], U[j]\) を用意し、初期値を \(-\infty\) に設定します。
   • 初期状態として、キャンペーンを \(0\) 個選んで右端が \(0\) であるときの利益は \(0\) なので、 \(T[0][0] = 0\) とします。
3. DPの遷移:
   • 各キャンペーン \([L, R]\) について、順番に以下の処理を行います：
     • \(j = 1, 2, \ldots, K\) について、セグメント木から以下の値をクエリします。

          - $val_1 = (\text{query}(T[j-1], 0, L-1)) - S[L-1]$
          - $val_2 = \text{query}(U[j-1], L, R-1)$
          - $dp[j] = S[R] + \max(val_1, val_2)$
       

     • すべての \(j\) について \(dp[j]\) を計算し終えた後、セグメント木を更新します：

          - $T[j][R] \leftarrow \max(T[j][R], dp[j])$
          - $U[j][R] \leftarrow \max(U[j][R], dp[j] - S[R])$
       

4. 答えの出力:
   • これまでに得られた \(dp[j]\) の最大値（または \(T[K]\) の最大値）が答えとなります。

計算量

• 時間計算量: \(O(M \log M + K M \log N)\)
  • キャンペーンのソートに \(O(M \log M)\) かかります。
  • 各キャンペーン \(M\) 個に対して、個数 \(K\) のループを回し、セグメント木のクエリと更新（\(O(\log N)\)）を行うため、DPの遷移全体で \(O(K M \log N)\) となります。 \(K \le 10\) と非常に小さいため、十分高速に動作します。
• 空間計算量: \(O(K N + M)\)
  • サイズ \(O(N)\) のセグメント木を \(2(K+1)\) 個保持するため、空間計算量は \(O(K N)\) となり、メモリ制限にも十分余裕があります。

実装のポイント

• 1ベースインデックスと0ベースインデックス:

  • 累積和 \(S\) や商品のインデックスは \(1\) ベースで扱うと、区間の左端 \(L-1\) などを自然に表現できて実装がシンプルになります。

• バッチ処理（更新のタイミング）:

  • 各キャンペーン \([L, R]\) の処理において、同じキャンペーンから得られた \(dp[j-1]\) の更新結果が、同一ステップ内の \(dp[j]\) の計算に影響を与えないようにする必要があります。そのため、各 \(j\) について一時変数に計算結果を保持し、すべての \(j\) について計算が終わってからセグメント木を更新します。

    ソースコード

import sys

def solve():
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    N = int(input_data[0])
    M = int(input_data[1])
    K = int(input_data[2])
    
    V = [int(x) for x in input_data[3:3+N]]
    
    S = [0] * (N + 1)
    for i in range(N):
        S[i+1] = S[i] + V[i]
        
    intervals = []
    idx = 3 + N
    for _ in range(M):
        l = int(input_data[idx])
        r = int(input_data[idx+1])
        intervals.append((l, r))
        idx += 2
        
    intervals.sort()
    
    size = 1
    while size < N + 1:
        size *= 2
        
    INF = 10**18
    
    T = [[-INF] * (2 * size) for _ in range(K + 1)]
    U = [[-INF] * (2 * size) for _ in range(K + 1)]
    
    T_0 = T[0]
    curr = size
    T_0[curr] = 0
    while curr > 1:
        curr >>= 1
        T_0[curr] = 0
        
    ans = 0
    dp = [0] * (K + 1)
    
    def query(tree, l, r, size=size, INF=INF):
        if l > r:
            return -INF
        res = -INF
        l += size
        r += size + 1
        while l < r:
            if l & 1:
                if tree[l] > res:
                    res = tree[l]
                l += 1
            if r & 1:
                r -= 1
                if tree[r] > res:
                    res = tree[r]
            l >>= 1
            r >>= 1
        return res

    def update(tree, idx, val, size=size):
        idx += size
        if val > tree[idx]:
            tree[idx] = val
            while idx > 1:
                idx >>= 1
                left = tree[2 * idx]
                right = tree[2 * idx + 1]
                tree[idx] = left if left > right else right

    for L, R in intervals:
        s_R = S[R]
        s_L_minus_1 = S[L - 1]
        
        for j in range(1, K + 1):
            t_tree = T[j-1]
            val1 = query(t_tree, 0, L - 1) - s_L_minus_1
            
            u_tree = U[j-1]
            val2 = query(u_tree, L, R - 1)
            
            best = val1 if val1 > val2 else val2
            dp[j] = s_R + best
            if dp[j] > ans:
                ans = dp[j]
                
        for j in range(1, K + 1):
            val = dp[j]
            if val != -INF:
                update(T[j], R, val)
                update(U[j], R, val - s_R)
                
    print(ans)

if __name__ == '__main__':
    solve()

---

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