Official

E - 広告キャンペーンの選択 / Selection of Advertising Campaigns Editorial by admin Editorial for printing

gpt-5.5-high

概要

商品を重み付きの点列、広告キャンペーンを区間とみなし、ちょうど \(K\) 個の区間を選んだときの和集合の重み最大値を求めます。

区間の包含関係を取り除いたあと、DP としゃくとり法・単調キューを使って \(O(M \log M + KM)\) で解きます。

考察

「ちょうど \(K\) 個」は「高々 \(K\) 個」と考えてよい

商品の利益 \(V_i\) はすべて正です。

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

したがって、

  • 高々 \(K\) 個選んだときの最大値
  • ちょうど \(K\) 個選んだときの最大値

は同じになります。

高々 \(K\) 個で得られる最適解が \(K\) 個未満のキャンペーンしか使っていない場合でも、適当なキャンペーンを追加すれば利益は減らず、ちょうど \(K\) 個にできます。

含まれる区間は不要

例えば、あるキャンペーンの区間が \([2, 5]\)、別のキャンペーンの区間が \([3, 4]\) だとします。

このとき \([3, 4]\) は \([2, 5]\) に完全に含まれています。

\([3, 4]\) を選ぶくらいなら、代わりに \([2, 5]\) を選んでも利益は減りません。

そのため、他の区間に完全に含まれる区間は、最適値を求める上では削除して構いません。

区間を

  • 左端 \(L\) の昇順
  • 左端が同じなら右端 \(R\) の降順

でソートします。

その後、左から順に見て、これまでに見た最大の右端よりも右端が大きい区間だけを残します。

これにより、残った区間については

\[ L_0 < L_1 < \cdots < L_{m-1} \]

かつ

\[ R_0 < R_1 < \cdots < R_{m-1} \]

が成り立ちます。

つまり、残った区間は左端も右端も単調に増加します。

素朴な DP は重すぎる

残った区間数を \(m\) とします。

\(dp_t[i]\) を

\(t\) 個の区間を選び、最後に選んだ区間が \(i\) であるときの最大利益

とします。

区間 \(i\) の直前に選ぶ区間を \(j\) とすると、普通に全ての \(j < i\) を試すと、各 \(t\) について \(O(m^2)\) かかります。

\(K \leq 10\) とはいえ、\(m\) は最大 \(10^5\) なので、\(O(Km^2)\) は間に合いません。

そこで、遷移を工夫して \(O(Km)\) にします。

区間を追加したときの増分

累積和を

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

とします。

区間 \(i\) を \([L_i, R_i]\) とすると、その区間単体の利益は

\[ S_{R_i} - S_{L_i - 1} \]

です。

ここで、

\[ A_i = S_{L_i - 1} \]

\[ B_i = S_{R_i} \]

と置きます。

区間 \(j\) の後に区間 \(i\) を選ぶことを考えます。

残した区間は \(L\) も \(R\) も増加しているので、\(j < i\) なら

\[ L_j < L_i,\quad R_j < R_i \]

です。

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

\[ R_j < L_i \]

なら、区間 \(i\) は丸ごと新しく利益に加わります。

増分は

\[ B_i - A_i \]

です。

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

\[ R_j \geq L_i \]

なら、区間 \(i\) のうち、\([L_i, R_j]\) はすでに区間 \(j\) によってカバーされています。

したがって、新しく増える部分は \(R_j+1\) から \(R_i\) までで、増分は

\[ B_i - B_j \]

です。

DP の遷移式

以上より、\(dp_t[i]\) は次のように表せます。

\[ dp_t[i] = \max_{j < i} \begin{cases} dp_{t-1}[j] + B_i - A_i & (R_j < L_i) \\ dp_{t-1}[j] + B_i - B_j & (R_j \geq L_i) \end{cases} \]

これを整理すると、

\[ dp_t[i] = B_i + \max \left( \max_{j < i, R_j < L_i}(dp_{t-1}[j] - A_i), \max_{j < i, R_j \geq L_i}(dp_{t-1}[j] - B_j) \right) \]

です。

ここで、\(A_i\) は \(i\) ごとに固定なので、前半は

\[ \max_{j < i, R_j < L_i} dp_{t-1}[j] - A_i \]

を求めればよいです。

また、後半は

\[ \max_{j < i, R_j \geq L_i}(dp_{t-1}[j] - B_j) \]

を求めればよいです。

高速化

残った区間では \(R_i\) が単調増加しています。

そのため、各 \(i\) について

\[ R_j < L_i \]

を満たす最大範囲は、ある位置 \(p\) より前の区間になります。

つまり、

  • \(j < p\) は区間 \(i\) と重ならない
  • \(p \leq j < i\) は区間 \(i\) と重なる

という形になります。

重ならない区間の最大値

\[ \max_{j < p} dp_{t-1}[j] \]

が必要です。

これは前からの最大値 pref_dp を用意すれば \(O(1)\) で求められます。

重なる区間の最大値

\[ \max_{p \leq j < i}(dp_{t-1}[j] - B_j) \]

が必要です。

これは範囲 \([p, i-1]\) の最大値です。

\(i\) が増えるにつれて、範囲の右端も左端も右に動くだけなので、単調キューを使うと全体で \(O(m)\) で処理できます。

アルゴリズム

  1. 累積和 \(S\) を計算する。
  2. 区間を \((L, -R)\) でソートする。
    • これにより、\(L\) 昇順、同じ \(L\) では \(R\) 降順になる。
  3. 左から見て、これまでの最大右端より大きい \(R\) を持つ区間だけを残す。
    • 含まれる区間を削除する。
  4. 残った区間について、配列を用意する。
    • Ls[i] = L_i
    • Rs[i] = R_i
    • SL[i] = S_{L_i - 1}
    • SR[i] = S_{R_i}
  5. \(1\) 個だけ選ぶ場合の DP を初期化する。

\[ dp[i] = SR[i] - SL[i] \]

  1. 選ぶ個数を \(2\) 個から \(\min(K, m)\) 個まで増やしながら DP する。
    • pref_dp[i] = max(dp[0], ..., dp[i])
    • minus[i] = dp[i] - SR[i]
    • 単調キューで、重なる区間候補の minus の最大値を管理する。
  2. 各段階の最大値を答え候補として更新する。
  3. 最終的な最大値を出力する。

計算量

  • 時間計算量: \(O(M \log M + KM)\)
    • 区間のソートに \(O(M \log M)\)
    • DP に \(O(Km)\)、ただし \(m \leq M\)
  • 空間計算量: \(O(M)\)

実装のポイント

  • 利益の合計は最大で \(10^5 \times 10^9 = 10^{14}\) 程度になるため、64 bit 整数が必要です。
    • Python では int で問題ありません。
  • 区間 \([L, R]\) の利益は累積和を使って

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

で求めます。

  • 区間の重なり判定では、商品番号は整数なので

\[ R_j < L_i \]

なら非重複です。

\[ R_j = L_i \]

の場合は商品 \(L_i\) を共有しているため、重なっている扱いになります。

  • 削除後の区間数 \(m\) が \(K\) より小さい場合もあります。

    • その場合は \(\min(K, m)\) 個までの DP を行えば十分です。

    • 元の問題では削除した区間を「追加で選ぶ」ことで、ちょうど \(K\) 個に調整できます。

      ソースコード

import sys

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    N, M, K = data[0], data[1], data[2]

    pref = [0] * (N + 1)
    acc = 0
    idx = 3
    for i in range(1, N + 1):
        acc += data[idx]
        pref[i] = acc
        idx += 1

    intervals = [(data[i], -data[i + 1]) for i in range(idx, idx + 2 * M, 2)]
    intervals.sort()

    Ls = []
    Rs = []
    SL = []
    SR = []

    max_r = 0
    for l, nr in intervals:
        r = -nr
        if r > max_r:
            Ls.append(l)
            Rs.append(r)
            SL.append(pref[l - 1])
            SR.append(pref[r])
            max_r = r

    m = len(Ls)

    dp = [SR[i] - SL[i] for i in range(m)]
    ans = max(dp)

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

    for _ in range(2, limit + 1):
        pref_dp = [0] * m
        minus = [0] * m

        mx = NEG
        for i in range(m):
            v = dp[i]
            if v > mx:
                mx = v
            pref_dp[i] = mx
            minus[i] = v - SR[i]

        cur = [NEG] * m
        q = [0] * m
        head = 0
        tail = 0
        p = 0
        layer_max = NEG

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

            li = Ls[i]
            while Rs[p] < li:
                p += 1

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

            best = NEG
            if p > 0:
                v = pref_dp[p - 1] - SL[i]
                if v > best:
                    best = v
            if head < tail:
                v = minus[q[head]]
                if v > best:
                    best = v

            val = SR[i] + best
            cur[i] = val
            if val > layer_max:
                layer_max = val

        if layer_max > ans:
            ans = layer_max
        dp = cur

    print(ans)

if __name__ == "__main__":
    main()

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

posted:
last update: