Educational Codeforces Round 98 E - Two Editorials - 輪郭をなぞるだけのブログ

難しい、全然分からんかった。

リンク

問題概要 (雑)

長さ $n$ の区間があり、 $m$ 個の区間が $[l_{i}, r_{i}]$ の形式で与えられる。これらの区間を $2$ つのグループに分けることを考える。(各区間はただ一つのグループに属し、複数個には属さない。) 各グループでは長さ $k$ の区間を一つだけ設置して、この区間と $i$ 番目の区間との重複している長さを $a_{i}$ とする。このときの $\sum_{i=1}^{m} a_{i}$ を最大化する。

制約

$1 \leq n, m \leq 2000$
$1 \leq k \leq n$
$1 \leq l_{i} \leq r_{i} \leq n$

(考察)

愚直解として、 $2$ つの区間をどこにするか決めて、毎回 $m$ 個の区間をどちらかに割り当てるという処理が考えられる。
これは、 $O(n^2 m)$ で間に合わない。

以下の気付きが重要である。
長さの等しい $2$ つの区間 $[x, x + k), [y, y + k)$ があるとき、 $i$ 番目の区間がどちらに属した方が得であるか。
これは、それぞれの区間の中央値を比較すればよく、中央値が近い方を選択する。
他方を選んでも得をしないことから示せる。(らしい)
これ天才すぎる、全然気付かなかった。

この事実を活かすために、 $m$ 個の区間を中央値に関連する値 ( $=l_{i}+r_{i}$ ) でソートしておく。
この数列における区切り線を全探索する。
区切り線より左側は中央値が左側の区間に、区切り線より右側は中央値が右側の区間に属する、と考えることができる。
区切り線を固定したときに、長さ $k$ の区間をどこに設置すればよいかは、各グループで累積和を取っておいて全探索すればよい。
ここまでの処理は、 $O(m\log{m} + m(m + n))$ で実現でき、制限時間内に答えを求めることができる。

難しすぎて困った。

コード

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

using P = pair<int, int>;

template<class T>
inline bool chmax(T& x, T y){
    if(x < y){
        x = y;
        return true;
    }
    return false;
}

int main(){
    int n, m, k;
    cin >> n >> m >> k;
    vector<P> sections(m);
    for(auto& [l, r] : sections){
        cin >> l >> r;
        --l;
    }
    
    // (l + r) 昇順にソート
    sort(sections.begin(), sections.end(), [](const P& a, const P& b){
        return a.first + a.second < b.first + b.second;
    });
    
    // 区間を prefix, suffix の 2 つのグループに分ける
    vector<int> prefix(n + 1), suffix(n + 1), prefix_sum(n + 1), suffix_sum(n + 1);
    int ans = 0;
    
    // 区切り線を全探索
    for(int i = 0; i < m; ++i){
        // 位置 j を横切る区間が何個あるかを imos 法で求めておく
        for(int j = 0; j <= n; ++j) prefix[j] = suffix[j] = 0;
        for(int j = 0; j < i; ++j){
            auto [l, r] = sections[j];
            prefix[l] += 1;
            prefix[r] -= 1;
        }
        for(int j = i; j < m; ++j){
            auto [l, r] = sections[j];
            suffix[l] += 1;
            suffix[r] -= 1;
        }
        for(int j = 0; j < n; ++j){
            prefix[j + 1] += prefix[j];
            suffix[j + 1] += suffix[j];
        }
        
        // 重複する長さの合計を累積和から取得できるようにする
        prefix_sum[0] = suffix_sum[0] = 0;
        for(int j = 0; j < n; ++j){
            prefix_sum[j + 1] = prefix_sum[j] + prefix[j];
            suffix_sum[j + 1] = suffix_sum[j] + suffix[j];
        }
        
        // 長さ k の区間を置く場所を全探索
        int prefix_cnt = 0, suffix_cnt = 0;
        for(int j = 0; j + k <= n; ++j){
            chmax(prefix_cnt, prefix_sum[j + k] - prefix_sum[j]);
            chmax(suffix_cnt, suffix_sum[j + k] - suffix_sum[j]);
        }
        
        chmax(ans, prefix_cnt + suffix_cnt);
    }
    
    cout << ans << '\n';
}

雑記

雑なメモなので、あとで修正したりするかもしれない。