E - 読書マラソン / Reading Marathon Editorial by admin
gpt-5.5-highOverview
This is a problem of finding the maximum total length of the union of intervals when selecting at most \(K\) intervals \([L_i, R_i]\).
We solve it using dynamic programming, taking advantage of the fact that \(K \leq 10\) is small.
Analysis
First, each reading plan can be thought of as an interval.
What we want to find is the number of integer points that can be covered when selecting at most \(K\) intervals, i.e., the length of the union of intervals.
A naive approach is too slow
There are up to \(M = 10^5\) intervals.
If we enumerate all possible selections of at most \(K\) intervals from them,
\[ \binom{M}{K} \]
combinations arise, and even though \(K \leq 10\), this is far too slow.
Also, since \(N \leq 10^9\), we cannot create an array that manages each book individually.
Therefore, we think efficiently using only the endpoints of the intervals.
Contained intervals are unnecessary
For example, suppose we have the following intervals:
- \([2, 10]\)
- \([4, 7]\)
\([4, 7]\) is completely contained within \([2, 10]\).
In this case, rather than selecting \([4, 7]\), selecting \([2, 10]\) instead will never decrease the number of book types we can read.
Therefore, intervals that are completely contained within another interval can be removed.
In the code, we sort the intervals by:
- Ascending order of left endpoint \(L\)
- Descending order of right endpoint \(R\) when left endpoints are the same
Then, we keep only those intervals whose right endpoint is larger than the maximum right endpoint seen so far.
As a result, for the remaining intervals:
\[ L_0 < L_1 < \cdots < L_{n-1} \]
and
\[ R_0 < R_1 < \cdots < R_{n-1} \]
both hold.
This property is extremely important.
DP Formulation
Let the remaining intervals be numbered \(0, 1, \dots, n-1\) from left to right.
Define \(dp[t][i]\) as follows:
\[ dp[t][i] = \text{the maximum number of books that can be read when selecting } t \text{ intervals, with the rightmost interval being the } i\text{-th one} \]
Here, “rightmost” means having the largest index among the remaining intervals.
Since \(R\) is also in ascending order for the remaining intervals, a larger index means a larger right endpoint.
Length gained when adding an interval
Suppose we have already selected \(t-1\) intervals, and the last one is the \(j\)-th interval.
We add the \(i\)-th interval, where \(j < i\).
The additional length gained is as follows:
1. Non-overlapping case
If
\[ R_j < L_i \]
then all intervals up to interval \(j\) do not overlap with the \(i\)-th interval.
Therefore, the length gained is simply the length of the \(i\)-th interval itself:
\[ R_i - L_i + 1 \]
2. Overlapping case
If
\[ R_j \geq L_i \]
then interval \(j\) overlaps with interval \(i\).
Since \(L_j < L_i\) for the remaining intervals, interval \(j\) already covers from \(L_i\) to \(R_j\).
Therefore, the newly gained portion is from \(R_j+1\) to \(R_i\).
The length gained is:
\[ R_i - R_j \]
Therefore, the transition is:
\[ dp[t][i] = \max_{j < i} \begin{cases} dp[t-1][j] + (R_i - L_i + 1) & (R_j < L_i) \\ dp[t-1][j] + (R_i - R_j) & (R_j \geq L_i) \end{cases} \]
However, computing this directly takes \(O(Kn^2)\) time, and since \(n\) can be up to \(10^5\), this is too slow.
Speeding up the transition
Since \(R\) is in ascending order, for a given \(i\):
- The \(j\) values satisfying \(R_j < L_i\)
- The \(j\) values satisfying \(R_j \geq L_i\)
can be separated using binary search.
In the code, the boundary value used is:
\[ L_i - 1 \]
When \(R_j = L_i - 1\), the intervals don’t actually overlap, but:
\[ R_i - R_j = R_i - (L_i - 1) = R_i - L_i + 1 \]
which equals the value when adding the entire interval.
Therefore, including it on the overlapping side causes no issues.
For the non-overlapping side, we want to maximize:
\[ dp[t-1][j] + (R_i - L_i + 1) \]
so we only need to know the maximum of:
\[ dp[t-1][j] \]
This is managed with a prefix max.
For the overlapping side, we want to maximize:
\[ dp[t-1][j] + R_i - R_j \]
Looking at this for a fixed \(i\), \(R_i\) is constant, so we only need to know the maximum of:
\[ dp[t-1][j] - R_j \]
This becomes a range maximum query, which is managed with a segment tree.
Algorithm
Read the intervals as input.
Sort the intervals in the following order:
- Ascending order of \(L\)
- Descending order of \(R\) when \(L\) is the same
Remove intervals contained within other intervals.
- Let
maxRbe the maximum right endpoint seen so far. - Keep only intervals where \(R_i > maxR\).
- Let
Let the number of remaining intervals be \(n\).
Perform DP.
- When \(t = 1\):
$\( dp[1][i] = R_i - L_i + 1 \)$
- When \(t \geq 2\):
- Build a prefix max from the previous DP values
prev. - Build a segment tree with \(prev[j] - R_j\) as values.
- For each \(i\), find the boundary using binary search.
- Compute the maximum from the non-overlapping case and the overlapping case.
- Build a prefix max from the previous DP values
The answer is the maximum DP value across \(t = 1\) to \(K\).
Complexity
- Time complexity: \(O(M \log M + K n \log n)\)
- Sorting: \(O(M \log M)\)
- DP: \(O(K n \log n)\)
- \(n\) is the number of intervals after removing unnecessary ones, with \(n \leq M\)
- Space complexity: \(O(n)\)
Implementation Notes
Since \(N\) can be up to \(10^9\), we do not create a per-book array.
Interval lengths and DP values are handled with
long long.Unreachable DP states are filled with a sufficiently small value
NEG.The segment tree retrieves the maximum value over a range \([l, r)\).
Since the problem asks for “at most \(K\)” intervals, we take the maximum DP value from \(1\) to \(K\), not exactly \(K\).
Source Code
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll NEG = -(1LL << 60);
struct SegTree {
int n;
vector<ll> seg;
SegTree() {}
SegTree(const vector<ll>& v) { build(v); }
void build(const vector<ll>& v) {
int sz = (int)v.size();
n = 1;
while (n < sz) n <<= 1;
seg.assign(2 * n, NEG);
for (int i = 0; i < sz; i++) seg[n + i] = v[i];
for (int i = n - 1; i >= 1; i--) seg[i] = max(seg[i << 1], seg[i << 1 | 1]);
}
ll query(int l, int r) {
ll res = NEG;
l += n;
r += n;
while (l < r) {
if (l & 1) res = max(res, seg[l++]);
if (r & 1) res = max(res, seg[--r]);
l >>= 1;
r >>= 1;
}
return res;
}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
ll N;
int M, K;
cin >> N >> M >> K;
vector<pair<ll, ll>> intervals(M);
for (int i = 0; i < M; i++) {
cin >> intervals[i].first >> intervals[i].second;
}
sort(intervals.begin(), intervals.end(), [](const auto& a, const auto& b) {
if (a.first != b.first) return a.first < b.first;
return a.second > b.second;
});
vector<ll> L, R, len;
ll maxR = 0;
for (auto [l, r] : intervals) {
if (r > maxR) {
L.push_back(l);
R.push_back(r);
len.push_back(r - l + 1);
maxR = r;
}
}
int n = (int)L.size();
K = min(K, n);
vector<ll> prev(n, NEG), curr(n, NEG);
ll ans = 0;
for (int t = 1; t <= K; t++) {
fill(curr.begin(), curr.end(), NEG);
if (t == 1) {
for (int i = 0; i < n; i++) {
curr[i] = len[i];
}
} else {
vector<ll> vals(n, NEG);
for (int i = 0; i < n; i++) {
if (prev[i] > NEG / 2) vals[i] = prev[i] - R[i];
}
SegTree seg(vals);
vector<ll> pref(n + 1, NEG);
for (int i = 0; i < n; i++) {
pref[i + 1] = max(pref[i], prev[i]);
}
for (int i = 0; i < n; i++) {
ll threshold = L[i] - 1;
int q = lower_bound(R.begin(), R.begin() + i, threshold) - R.begin();
ll best = NEG;
if (pref[q] > NEG / 2) {
best = max(best, pref[q] + len[i]);
}
ll overlap = seg.query(q, i);
if (overlap > NEG / 2) {
best = max(best, overlap + R[i]);
}
curr[i] = best;
}
}
for (ll x : curr) ans = max(ans, x);
swap(prev, curr);
}
cout << ans << '\n';
return 0;
}
This editorial was generated by gpt-5.5-high.
posted:
last update: