E - 広告キャンペーンの選択 / Selection of Advertising Campaigns Editorial by admin Editorial for printing
gemini-3.5-flash-thinking概要
この問題は、\(N\) 個の商品からちょうど \(K\) 個のキャンペーンを選択し、カバーされる商品の利益の総和を最大化する問題です。
キャンペーン同士の重複を正しく処理しつつ、キャンペーンの包含関係を整理して無駄な選択肢を省くことで、動的計画法（DP）とセグメント木（RMQ: Range Maximum Query）を用いた高速な遷移が可能になります。
考察
素朴なアプローチと課題
キャンペーンの選び方は \(\binom{M}{K}\) 通りあります。\(M \le 10^5\)、 \(K \le 10\) であるため、愚直にすべての組み合わせを試すことは不可能です。また、選んだキャンペーンの区間が重複している場合、重複部分の利益を二重に加算しないように注意する必要があります。
重要な観察1：不要なキャンペーンの排除
あるキャンペーン \(A\) が別のキャンペーン \(B\) に完全に含まれている（\(L_B \le L_A \le R_A \le R_B\)）とします。 各商品の利益は \(V_i \ge 1\) であるため、キャンペーン \(A\) を選ぶくらいなら、より広い範囲をカバーするキャンペーン \(B\) を選んだ方が、得られる利益は必ず以上になります。
したがって、他のキャンペーンに完全に内包されるキャンペーンは、あらかじめすべて取り除いてしまって構いません。
重要な観察2：区間の整理
不要なキャンペーンを排除し、左端 \(L\) の昇順（同じなら右端 \(R\) の降順）でソートすると、残ったキャンペーンには非常に強力な性質が現れます。 それは、「インデックスが進むにつれて、左端 \(L\) も右端 \(R\) も狭義単調増加する」 という性質です。 すなわち、残った \(M'\) 個のキャンペーンは以下を満たします。 $\(L_1 < L_2 < \dots < L_{M'}\)\( \)\(R_1 < R_2 < \dots < R_{M'}\)$
DPによるアプローチ
この単調性を利用して、左から順にキャンペーンを選んでいく動的計画法（DP）を考えます。
- \(\text{dp}[j][i]\) : キャンペーンを \(j\) 個選び、最後に選んだのがキャンペーン \(i\) であるときの最大利益
\(j\) 個目にキャンペーン \(i\) を選び、その直前（\(j-1\) 個目）にキャンペーン \(p\) (\(p < i\)) を選んだとします。このとき、新しく得られる利益は区間の重なり方によって以下の2パターンに分かれます。
重なりがない場合 (\(R_p < L_i\)) 区間が完全に離れているため、新しくカバーされるのは \([L_i, R_i]\) 全体です。 得られる追加の利益は \(S[R_i] - S[L_i - 1]\) となります（\(S\) は \(V\) の累積和配列）。 $\(\text{dp}[j][i] = \text{dp}[j-1][p] + S[R_i] - S[L_i - 1]\)$
重なりがある場合 (\(R_p \ge L_i\)) キャンペーン \(p\) と \(i\) は重なっていますが、単調性より \(R_p < R_i\) です。したがって、新しくカバーされるのは \((R_p, R_i]\) の範囲となります。 得られる追加の利益は \(S[R_i] - S[R_p]\) となります。 $\(\text{dp}[j][i] = \text{dp}[j-1][p] + S[R_i] - S[R_p]\)$
アルゴリズム
DPの遷移をそのまま行うと \(O(K M'^2)\) かかり、実行時間制限に間に合いません。そこで、二分探索とセグメント木を用いて遷移を高速化します。
各 \(j\) (\(1 \le j \le K\)) のループにおいて、\(\text{dp}[j-1]\) の値から \(\text{dp}[j]\) を更新します。
キャンペーン \(i\) に遷移するとき、 \(R_p < L_i\) を満たす最大の \(p\) を mid とします。これは \(R\) の単調性から二分探索（lower_bound）で \(O(\log M')\) で求まります。
1. 重なりがない場合（\(p \le \text{mid}\)）
求める値は以下の通りです。 $\(\max_{p \le \text{mid}} (\text{dp}[j-1][p]) - S[L_i - 1] + S[R_i]\)\( \)\text{dp}[j-1][p]\( の累積最大値を前計算（`pref_max`）しておくことで、\)\max_{p \le \text{mid}} \text{dp}[j-1][p]\( は \)O(1)$ で取得できます。
2. 重なりがある場合（\(\text{mid} < p < i\)）
求める値は以下の通りです。 $\(\max_{\text{mid} < p < i} (\text{dp}[j-1][p] - S[R_p]) + S[R_i]\)\( あらかじめ配列 \)A[p] = \text{dp}[j-1][p] - S[R_p]\( を構築し、これをセグメント木に乗せておきます。これにより、範囲 \)[\text{mid} + 1, i - 1]\( における \)A[p]\( の最大値を \)O(\log M’)$ で取得できます。
これら2つのケースの最大値を比較し、大きい方で \(\text{dp}[j][i]\) を更新します。
計算量
時間計算量: \(O(M \log M + K M \log M)\)
- キャンペーンのソートに \(O(M \log M)\)。
- 不要なキャンペーンのフィルタリングに \(O(M)\)。
- DPの各ステップ（\(K\) 回）において、セグメント木の構築に \(O(M)\)、各 \(i\) に対する二分探索とセグメント木クエリに \(O(\log M)\) かかります。
- 全体として \(O(M \log M + K M \log M)\) となり、 \(K \le 10\) のため非常に高速に動作します。
空間計算量: \(O(N + M)\)
- 累積和配列、キャンペーンのリスト、およびDPテーブル（直前の行のみ保持すればよいため \(O(M)\)）、セグメント木を保持するために必要なメモリです。
実装のポイント
不要なキャンペーンの削除: ソート後に「これまでに現れた最大の右端
max_R」を保持しながら走査することで、自身より左から始まり、かつ自身の右端以下で終わる（＝完全に内包される）キャンペーンを \(O(M)\) で簡単に取り除くことができます。メモリの節約: DPテーブル全体（\(K \times M\)）を保持する必要はありません。遷移には \(j-1\) の結果しか使わないため、
prev_dpとnext_dpの2本の配列を用意して、ループの最後にmoveでスワップすることで空間計算量を節約できます。ソースコード
#include <iostream>
#include <vector>
#include <algorithm>
#include <atcoder/segtree>
using namespace std;
using namespace atcoder;
const long long INF = 1e18;
long long op(long long a, long long b) {
return max(a, b);
}
long long e() {
return -INF;
}
struct Campaign {
int L, R;
};
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int N, M, K;
if (!(cin >> N >> M >> K)) return 0;
vector<long long> V(N + 1);
vector<long long> S(N + 1, 0);
for (int i = 1; i <= N; ++i) {
cin >> V[i];
S[i] = S[i - 1] + V[i];
}
vector<Campaign> campaigns(M);
for (int i = 0; i < M; ++i) {
cin >> campaigns[i].L >> campaigns[i].R;
}
// Sort campaigns: L ascending, then R descending
sort(campaigns.begin(), campaigns.end(), [](const Campaign& a, const Campaign& b) {
if (a.L != b.L) return a.L < b.L;
return a.R > b.R;
});
// Remove redundant campaigns (those fully contained in another)
vector<Campaign> filtered;
int max_R = 0;
for (const auto& c : campaigns) {
if (c.R > max_R) {
filtered.push_back(c);
max_R = c.R;
}
}
int M_prime = filtered.size();
K = min(K, M_prime);
vector<int> R_arr(M_prime + 1, 0);
for (int i = 0; i < M_prime; ++i) {
R_arr[i + 1] = filtered[i].R;
}
vector<long long> prev_dp(M_prime + 1, -INF);
prev_dp[0] = 0;
long long ans = 0;
for (int j = 1; j <= K; ++j) {
vector<long long> next_dp(M_prime + 1, -INF);
vector<long long> pref_max(M_prime + 1, -INF);
pref_max[0] = prev_dp[0];
for (int p = 1; p <= M_prime; ++p) {
pref_max[p] = max(pref_max[p - 1], prev_dp[p]);
}
vector<long long> seg_init(M_prime);
for (int p = 1; p <= M_prime; ++p) {
if (prev_dp[p] == -INF) {
seg_init[p - 1] = -INF;
} else {
seg_init[p - 1] = prev_dp[p] - S[R_arr[p]];
}
}
segtree<long long, op, e> seg(seg_init);
for (int i = 1; i <= M_prime; ++i) {
int L_i = filtered[i - 1].L;
int R_i = filtered[i - 1].R;
// Find largest p such that R_p < L_i
auto it = lower_bound(R_arr.begin(), R_arr.end(), L_i);
int mid = distance(R_arr.begin(), it) - 1;
long long max_left = pref_max[mid];
long long max_right = -INF;
int q_l = mid + 1;
int q_r = i - 1;
if (q_l <= q_r) {
max_right = seg.prod(q_l - 1, q_r);
}
long long val1 = (max_left == -INF) ? -INF : (max_left - S[L_i - 1]);
long long val2 = max_right;
long long best = max(val1, val2);
if (best != -INF) {
next_dp[i] = S[R_i] + best;
ans = max(ans, next_dp[i]);
}
}
prev_dp = move(next_dp);
}
cout << ans << "\n";
return 0;
}
この解説は gemini-3.5-flash-thinking によって生成されました。
posted:
last update: