解説 - AtCoder Weekday Contest 0114 Beta

公式

E - 広告キャンペーンの選択 / Selection of Advertising Campaigns 解説 by admin

gemini-3.5-flash-thinking

Overview

This problem asks us to select exactly $K$ campaigns from $N$ products, maximizing the total profit of covered products.

By properly handling overlaps between campaigns and organizing the inclusion relationships to eliminate redundant choices, we can achieve fast transitions using dynamic programming (DP) and a segment tree (RMQ: Range Maximum Query).

Analysis

Naive Approach and Challenges

There are $\binom{M}{K}$ ways to choose campaigns. Since $M \le 10^5$ and $K \le 10$, it is impossible to try all combinations naively. Additionally, when selected campaigns have overlapping intervals, we must be careful not to double-count the profit of overlapping portions.

Key Observation 1: Eliminating Redundant Campaigns

Suppose a campaign $A$ is completely contained within another campaign $B$ ($L_B \le L_A \le R_A \le R_B$). Since each product’s profit satisfies $V_i \ge 1$, instead of selecting campaign $A$, selecting campaign $B$ which covers a wider range will always yield at least as much profit.

Therefore, campaigns that are completely contained within other campaigns can be removed in advance.

Key Observation 2: Organizing Intervals

After eliminating redundant campaigns and sorting by left endpoint $L$ in ascending order (breaking ties by right endpoint $R$ in descending order), the remaining campaigns exhibit a very powerful property: “As the index increases, both the left endpoint $L$ and right endpoint $R$ are strictly increasing.” That is, the remaining $M'$ campaigns satisfy: $$L_1 < L_2 < \dots < L_{M'}$$R_1 < R_2 < \dots < R_{M'}$$

DP Approach

Utilizing this monotonicity, we consider a dynamic programming (DP) approach that selects campaigns from left to right.

$\text{dp}[j][i]$: The maximum profit when exactly $j$ campaigns are selected and the last one selected is campaign $i$

Suppose we select campaign $i$ as the $j$-th campaign, and the previous ($j-1$-th) campaign selected was campaign $p$ ($p < i$). The newly gained profit splits into the following 2 patterns depending on how the intervals overlap:

No overlap ($R_p < L_i$) The intervals are completely separated, so the newly covered range is the entirety of $[L_i, R_i]$. The additional profit gained is $S[R_i] - S[L_i - 1]$ (where $S$ is the prefix sum array of $V$). $$\text{dp}[j][i] = \text{dp}[j-1][p] + S[R_i] - S[L_i - 1]$$
Overlap exists ($R_p \ge L_i$) Campaigns $p$ and $i$ overlap, but by monotonicity $R_p < R_i$. Therefore, the newly covered range is $(R_p, R_i]$. The additional profit gained is $S[R_i] - S[R_p]$. $$\text{dp}[j][i] = \text{dp}[j-1][p] + S[R_i] - S[R_p]$$

Algorithm

If we perform the DP transitions directly, it takes $O(K M'^2)$, which exceeds the time limit. Therefore, we speed up transitions using binary search and a segment tree.

For each loop iteration $j$ ($1 \le j \le K$), we update $\text{dp}[j]$ from the values of $\text{dp}[j-1]$. When transitioning to campaign $i$, let mid be the largest $p$ satisfying $R_p < L_i$. This can be found in $O(\log M')$ using binary search (lower_bound) due to the monotonicity of $R$.

1. No overlap case ($p \le \text{mid}$)

The value we seek is: $$\max_{p \le \text{mid}} (\text{dp}[j-1][p]) - S[L_i - 1] + S[R_i]$$ By precomputing the prefix maximum of $\text{dp}[j-1][p]$ (`pref_max`), we can obtain $\max_{p \le \text{mid}} \text{dp}[j-1][p]$ in $O(1)$.

2. Overlap case ($\text{mid} < p < i$)

The value we seek is: $$\max_{\text{mid} < p < i} (\text{dp}[j-1][p] - S[R_p]) + S[R_i]$$ We construct the array $A[p] = \text{dp}[j-1][p] - S[R_p]$ in advance and load it into a segment tree. This allows us to obtain the maximum value of $A[p]$ in the range $[\text{mid} + 1, i - 1]$ in $O(\log M’)$.

We compare the maximum values from these two cases and update $\text{dp}[j][i]$ with the larger one.

Complexity

Time complexity: $O(M \log M + K M \log M)$
- Sorting campaigns takes $O(M \log M)$.
- Filtering redundant campaigns takes $O(M)$.
- In each DP step ($K$ iterations), building the segment tree takes $O(M)$, and for each $i$, binary search and segment tree queries take $O(\log M)$.
- Overall, this gives $O(M \log M + K M \log M)$, which runs very efficiently since $K \le 10$.
Space complexity: $O(N + M)$
- This is the memory needed to store the prefix sum array, the list of campaigns, the DP table (only the previous row needs to be kept, so $O(M)$), and the segment tree.

Implementation Notes

Removing redundant campaigns: After sorting, by maintaining “the maximum right endpoint seen so far max_R” while scanning, we can easily remove campaigns that start from the left and end at or before the current right endpoint (i.e., are completely contained) in $O(M)$.
Memory optimization: There is no need to store the entire DP table ($K \times M$). Since transitions only use the results from $j-1$, we can prepare two arrays prev_dp and next_dp, and swap them with move at the end of each loop to save space.

Source Code

#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;
}

This editorial was generated by gemini-3.5-flash-thinking.