概要

一直線上に配置された \(N\) 個の植え込みに対し、長さ \(D\) の範囲に水を撒けるスプリンクラーを1台設置し、水やりできない花の本数を最小化する問題です。

考察

• まず、水やりできない花の本数を最小化することは、水やり「できる」花の本数を最大化することと同じです。
• スプリンクラーを座標 \(s\) に設置した際、水が届く範囲は \(s \leq X_i < s + D\) です。この条件を満たす植え込みは、座標が大きい順に見ると連続した区間になります。
• 最適なスプリンクラーの設置位置 \(s\) を考えるとき、\(s\) をある植え込み \(l\) の座標 \(X_l\) にぴったり合わせれば、カバーできる範囲を無駄なく最大にすることができます。したがって、「左端を \(l\) 番目の植え込みに合わせる」という \(N\) 通りの配置だけを考えれば十分です。
• 各 \(l\) について、水が届く最も右側の植え込み \(r-1\) は \(X_{r-1} - X_l < D\) を満たす必要があります。すなわち、\(X_r - X_l \geq D\) となる直前まで \(r\) を進めます。
• すべての \(l\) について \(r\) を \(0\) から探すと計算量が \(O(N^2)\) となり、\(N \leq 2 \times 10^5\) の制約では実行時間制限超過（TLE）してしまいます。
• しかし、\(l\) を右に動かすと、条件 \(X_r - X_l < D\) を満たす \(r\) も必ず右方向に動く（またはそのまま）になります。この単調性を利用することで、\(l\) と \(r\) を同時に動かしながら調べる「尺取り法」が使えます。

アルゴリズム

尺取り法を用いて、水やりできる花の本数の最大値を求めます。 1. すべての植え込みの花の本数の合計 total を計算しておきます。 2. 左端 l を \(0\) から \(N-1\) までループで回します。 3. 右端 r が \(N\) 未満であり、かつ \(X_r - X_l < D\) を満たす限り、現在の区間内の花の本数の和 current_sum に \(P_r\) を足し、r を \(1\) 進めます。 4. current_sum がこれまでの最大値 ans_watered を上回れば、ans_watered を更新します。 5. l を \(1\) 進める前に、current_sum から \(P_l\) を引いておきます（区間から \(l\) 番目を外す）。 6. 最後に total - ans_watered が、水やりできない花の本数の最小値となります。

計算量

• 時間計算量: \(O(N)\) （尺取り法で左端 l と右端 r がそれぞれ最大 \(N\) 回しか動かないため）
• 空間計算量: \(O(N)\) （座標 \(X\) と花の本数 \(P\) を格納する配列のため）

実装のポイント

• 植え込みの座標 \(X_i\) や花の本数 \(P_i\) は最大 \(10^9\) であり、\(N\) も \(2 \times 10^5\) あるため、和を計算する際に32ビット整数（int型）ではオーバーフローします。合計値や最大値を保持する変数には64ビット整数（long long型）を使用する必要があります。

  ソースコード

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int N;
    long long D;
    if (!(cin >> N >> D)) return 0;
    
    vector<long long> X(N), P(N);
    long long total = 0;
    for (int i = 0; i < N; ++i) {
        cin >> X[i] >> P[i];
        total += P[i];
    }
    
    long long ans_watered = 0;
    long long current_sum = 0;
    int r = 0;
    
    for (int l = 0; l < N; ++l) {
        while (r < N && X[r] - X[l] < D) {
            current_sum += P[r];
            r++;
        }
        ans_watered = max(ans_watered, current_sum);
        current_sum -= P[l];
    }
    
    cout << total - ans_watered << "\n";
    
    return 0;
}

この解説は or-glm5.2-high によって生成されました。