概要

この問題は、数直線上に並んだ \(N\) 個の植え込みに対して、長さ \(D\) の区間（半開区間 \([s, s+D)\)）をうまく配置し、区間に含まれる花の本数の合計を最大化する問題です。 「水やりできない花の本数の最小値」は、「すべての花の本数の総和」から「水やりできる（区間に含まれる）花の本数の最大値」を引くことで求められます。

考察

1. スプリンクラーの設置位置の候補を絞り込む

スプリンクラーの設置位置 \(s\) は \(0\) 以上の任意の実数ですが、無限にある実数すべてを探索することは不可能です。 そこで、最適な設置位置の性質を考えます。

ある範囲 \([s, s+D)\) にいくつかの植え込みが含まれているとき、スプリンクラーの位置 \(s\) を右に動かしていくと、いずれかの植え込みが左端から外れる直前、すなわち \(s\) がいずれかの植え込みの座標 \(X_l\) と一致する瞬間 が存在します。 スプリンクラーの左端を植え込みの座標 \(X_l\) にぴったり合わせる（\(s = X_l\) とする）ことで、左端の植え込みをカバーしつつ、右端をできるだけ右側に伸ばすことができます。

したがって、探索すべきスプリンクラーの開始位置 \(s\) は、いずれかの植え込みの座標 \(X_l\) （\(1 \leq l \leq N\)）に一致するときのみを考えれば十分です。

2. 素朴なアプローチとその問題点

各植え込み \(l\) を左端としたとき、右端 \(r\) は \(X_r < X_l + D\) を満たす最大の植え込みとなります。 この範囲 \([l, r]\) に含まれる花の本数の総和を、すべての \(l\) について個別に計算するとどうなるでしょうか。

1つの \(l\) に対して \(r\) を探して合計を求めるのに \(O(N)\) の計算量がかかるため、全体で \(O(N^2)\) の計算量になります。 本問題の制約は \(N \leq 2 \times 10^5\) であるため、この方法では実行時間制限に間に合いません（TLEとなります）。

3. しゃくとり法による高速化

ここで、植え込みの座標が \(X_1 < X_2 < \cdots < X_N\) と昇順に並んでいることに注目します。 左端 \(l\) を右に動かしたとき、条件 \(X_r < X_l + D\) を満たす右端 \(r\) もまた、左に戻ることはなく右にのみ移動します（単調性）。

この性質を利用して、しゃくとり法（Two Pointers） を適用します。 左端 \(l\) を \(1\) つ進めるごとに、右端 \(r\) を条件を満たす限り右に進め、区間内の花の本数の合計を差分更新していくことで、各 \(l\) に対する最大値を効率よく求めることができます。

アルゴリズム

1. 初期化:

   • すべての花の本数の総和 total_P を計算します。
   • 区間内の花の本数の合計を表す変数 current_sum、その最大値を保持する max_covered を \(0\) で初期化します。
   • 右端を指すポインタ r を \(0\) に設定します。

2. しゃくとり法:

   • 左端のインデックス l を \(0\) から \(N-1\) まで順に進めます。
   • r が \(N\) 未満、かつ \(X_r < X_l + D\) を満たす間、current_sum に \(P_r\) を加え、r を \(1\) 進めます。
   • 条件を満たさなくなったら、その時点での current_sum と max_covered を比較し、最大値を更新します。
   • 次の l に進む前に、現在の左端の花の本数 \(P_l\) を current_sum から引きます。

3. 答えの出力:

   • total_P - max_covered が、水やりできない花の本数の最小値となります。

計算量

• 時間計算量: \(O(N)\)
  • l と r はそれぞれ \(0\) から \(N\) まで最大で \(1\) 回ずつしか増加しません。したがって、しゃくとり法のループ全体での遷移回数は高々 \(2N\) 回となり、全体で \(O(N)\) の時間計算量で処理できます。
• 空間計算量: \(O(N)\)
  • 入力された座標 \(X\) と花の本数 \(P\) を保持するための配列のメモリのみが必要となります。

実装のポイント

• オーバーフローへの対策:

  • 花の本数 \(P_i\) は最大で \(10^9\)、植え込みの数 \(N\) は最大で \(2 \times 10^5\) です。花の本数の総和は最大で \(2 \times 10^{14}\) に達するため、通常の32ビット整数型（C++の int など）ではオーバーフローします。合計値を扱う変数（total_P, current_sum, max_covered）には必ず64ビット整数型（C++の long long）を使用してください。

• 半開区間の条件:

  • スプリンクラーの散水範囲は \(s \leq X_i < s + D\)（\(s+D\) は未満）です。そのため、しゃくとり法の継続条件は X[r] < X[l] + D となり、等号を含めないように注意する必要があります。

    ソースコード

#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);
    vector<long long> P(N);
    long long total_P = 0;
    for (int i = 0; i < N; ++i) {
        cin >> X[i] >> P[i];
        total_P += P[i];
    }

    long long max_covered = 0;
    int r = 0;
    long long current_sum = 0;

    // しゃくとり法により、各左端 l に対してカバーできる最大の右端 r を求める
    for (int l = 0; l < N; ++l) {
        while (r < N && X[r] < X[l] + D) {
            current_sum += P[r];
            r++;
        }
        max_covered = max(max_covered, current_sum);
        current_sum -= P[l];
    }

    long long ans = total_P - max_covered;
    cout << ans << "\n";

    return 0;
}

---

この解説は gemini-3.5-flash-high によって生成されました。