概要

\(M\) 個の区間のうち連続する \(K\) 個をスキップしたときの塗装板数を最大化する問題。全区間の和集合から「スキップによる損失」を最小化する方針で解く。

考察

基本方針：全体から損失を引く

全 \(M\) 個の指示を実行した場合の塗装枚数（全区間の和集合の大きさ）を totalUnion とする。スキップ開始位置 \(s\) を選んだときの「損失」を \(\text{loss}(s)\) とすると、答えは：

\[\max_{s} (\text{totalUnion} - \text{loss}(s)) = \text{totalUnion} - \min_{s} \text{loss}(s)\]

損失の意味

あるセグメント（板の連続区間）が「損失」になるのは、そのセグメントを塗る指示がすべてスキップ範囲 \([s, s+K-1]\) に含まれる場合のみ。

セグメントごとの分析

座標圧縮後の各セグメントについて、そのセグメントをカバーする指示の中で： - 最小インデックス を \(\text{min\_idx}\) - 最大インデックス を \(\text{max\_idx}\)

とすると、このセグメントが損失になる条件は： $\(s \leq \text{min\_idx} \quad \text{かつ} \quad s + K - 1 \geq \text{max\_idx}\)$

整理すると、\(s\) の範囲は \([\text{max\_idx} - K + 1,\ \text{min\_idx}]\) となる。

素朴解の問題

各 \(s\) に対して愚直に損失を計算すると \(O(M \cdot N)\) で TLE。しかし差分配列を使えば、各セグメントの寄与を \(O(1)\) で記録し、最後にまとめて計算できる。

アルゴリズム

1. 座標圧縮: 各区間 \([L_i, R_i]\) を半開区間 \([L_i, R_i+1)\) として、境界値を集め、ソート・重複除去する。これにより最大 \(2M\) 個のセグメントに分割。

2. スイープライン: 座標圧縮されたセグメントを左から順に走査。各セグメントにおいてアクティブな指示集合（そのセグメントをカバーする指示のインデックス集合）を multiset で管理。

3. 差分配列で損失を記録: 各セグメントについて、アクティブ集合の最小・最大インデックスから、損失が発生する \(s\) の範囲 \([lo, hi]\) を計算し、差分配列に長さを加算。

4. 最小損失の計算: 差分配列を累積和して各 \(s\) に対する \(\text{loss}(s)\) を復元し、最小値を求める。

5. 答え: \(\text{totalUnion} - \min_s \text{loss}(s)\)

計算量

• 時間計算量: \(O(M \log M)\)（座標圧縮のソート、multiset操作が各 \(O(\log M)\) で計 \(O(M)\) 回）
• 空間計算量: \(O(M)\)（座標、イベント、差分配列の格納）

実装のポイント

• 座標圧縮: \(N\) が最大 \(10^9\) なので必須。半開区間 \([L_i, R_i+1)\) を使うと扱いやすい。

• イベントのソート: 同じ座標で終了イベント（type=0）が開始イベント（type=1）より先に処理されるよう、(座標, type, index) のタプルでソート。

• 1-indexed と 0-indexed の変換: コード内ではインデックスを 0-indexed で管理し、差分配列の計算時に 1-indexed に変換。

• \(lo > hi\) の場合: そのセグメントはどの \(s\) を選んでも損失にならない（スキップ範囲 \(K\) 個では全指示を含みきれない）。この場合はスキップ。

• long long の使用: \(N\) が大きいため、塗装枚数がオーバーフローしないよう注意。

  ソースコード

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    long long N;
    int M, K;
    cin >> N >> M >> K;
    
    vector<int> L(M), R(M);
    for (int i = 0; i < M; i++) {
        cin >> L[i] >> R[i];
    }
    
    // Collect coordinate boundaries (half-open intervals [L_i, R_i+1))
    vector<int> coords;
    for (int i = 0; i < M; i++) {
        coords.push_back(L[i]);
        coords.push_back(R[i] + 1);
    }
    sort(coords.begin(), coords.end());
    coords.erase(unique(coords.begin(), coords.end()), coords.end());
    
    // Events: (position, type, index) - type 0 = end, type 1 = start
    vector<tuple<int, int, int>> evts;
    for (int i = 0; i < M; i++) {
        evts.push_back({L[i], 1, i});
        evts.push_back({R[i] + 1, 0, i});
    }
    sort(evts.begin(), evts.end());
    
    multiset<int> active;
    long long totalUnion = 0;
    int evt_idx = 0;
    
    // Difference array for loss(s), s from 1 to M-K+1
    vector<long long> diff(M + 3, 0);
    
    for (int c = 0; c + 1 < (int)coords.size(); c++) {
        int left = coords[c];
        int right = coords[c + 1];
        long long len = (long long)(right - left);
        
        // Process all events at position 'left'
        // End events (type 0) come before start events (type 1) due to sorting
        while (evt_idx < (int)evts.size() && get<0>(evts[evt_idx]) == left) {
            auto [pos, type, idx] = evts[evt_idx];
            if (type == 1) active.insert(idx);
            else active.erase(active.find(idx));
            evt_idx++;
        }
        
        if (!active.empty()) {
            totalUnion += len;
            int min_idx = *active.begin() + 1;   // 1-indexed
            int max_idx = *active.rbegin() + 1;  // 1-indexed
            
            // This segment is lost when s in [max_idx - K + 1, min_idx]
            // intersected with [1, M - K + 1]
            int lo = max(1, max_idx - K + 1);
            int hi = min(M - K + 1, min_idx);
            
            if (lo <= hi) {
                diff[lo] += len;
                diff[hi + 1] -= len;
            }
        }
    }
    
    // Find minimum loss
    long long minLoss = LLONG_MAX;
    long long current = 0;
    for (int s = 1; s <= M - K + 1; s++) {
        current += diff[s];
        minLoss = min(minLoss, current);
    }
    
    cout << totalUnion - minLoss << endl;
    
    return 0;
}

---

この解説は claude4.6opus-thinking によって生成されました。