概要

数直線上の \(N\) 個の植え込みに対して、長さ \(D\) の半開区間 \([s, s+D)\) をうまく配置し、区間に含まれる花の本数を最大化（＝区間外にある水やりできない花の本数を最小化）する問題です。

考察

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

スプリンクラーの設置位置 \(s\) は \(0\) 以上の任意の実数ですが、無限にある実数すべてを探索することはできません。 ここで、最適な設置位置 \(s\) について考えてみましょう。

スプリンクラーの散水範囲は \([s, s+D)\) です。もし、散水範囲の左端 \(s\) がどの植え込みの座標とも一致しておらず、区間内にいくつかの植え込みが含まれているとします。このとき、スプリンクラーの位置を右にずらして、区間の左端 \(s\) を区間内にある最も左の植え込みの座標 \(X_i\) に一致させても、カバーできる植え込みが減ることはありません。むしろ、右側に余裕ができるため、より多くの植え込みをカバーできる可能性があります。

したがって、スプリンクラーの左端 \(s\) をいずれかの植え込みの座標 \(X_i\) に一致させる場合（\(s = X_i\)）のみを考えれば十分です。探索すべき \(s\) の候補は \(s = X_1, X_2, \dots, X_N\) の \(N\) 通りに絞られます。

2. 素朴な方法（全探索）の問題点

各 \(s = X_i\) について、区間 \([X_i, X_i+D)\) に含まれる植え込みを毎回 \(1\) つずつ確認して花の本数の合計を計算すると、1回あたり \(O(N)\) の計算量がかかります。これをすべての \(i\)（\(1 \leq i \leq N\)）について行うと、全体の計算量は \(O(N^2)\) となります。 本問題の制約は \(N \leq 2 \times 10^5\) であるため、これでは実行時間制限（通常2秒程度）に間に合わず、TLE（実行時間制限超過）になってしまいます。

3. 高速化のアイデア（単調性の利用）

植え込みの座標は \(X_1 < X_2 < \dots < X_N\) と昇順に並んでいます。 左端 \(s = X_{\text{left}}\) を右に進めると、それに対応する右端の境界 \(X_{\text{left}} + D\) も右に移動します。 このように、左端を進めたときに右端も右にしか進まないという「単調性」がある場合、しゃくとり法（Two Pointers）を用いることで、重複する計算を省いて高速に解くことができます。

アルゴリズム

しゃくとり法を用いて、各左端 left に対する右端 right を効率よく管理します。

1. 初期化:

   • 全ての花の本数の総和 total_flowers を計算しておきます。
   • 区間内の花の本数の最大値 max_sum を \(0\)、現在の区間の合計 current_sum を \(0\)、右端のポインタ right を \(0\) に初期化します。

2. しゃくとり法のループ:

   • 左端のポインタ left を \(0\) から \(N-1\) まで順に進めます。
   • 各 left について、X[right] < X[left] + D を満たす限り right を \(1\) ずつ進め、current_sum に P[right] を加算していきます。
   • right が進めなくなったら、その時点での current_sum と max_sum を比較し、最大値を更新します。
   • 次のループ（left を \(1\) 進める）の準備として、現在の左端にある花の本数 P[left] を current_sum から引きます。

3. 答えの出力:

   • 水やりできる花の本数の最大値は max_sum です。
   • 求めたいものは「水やりできない花の本数の最小値」なので、全体の総和から最大値を引いた total_flowers - max_sum が答えとなります。

具体例での動作

\(D = 5\)、植え込みの座標 \(X = [1, 2, 5, 7]\)、花の本数 \(P = [2, 3, 4, 1]\) の場合を考えます。

• left = 0 (\(X_0 = 1\)):

  • 許容範囲は \(1 + 5 = 6\) 未満。
  • right = 0 (\(X_0=1 < 6\)): current_sum に \(P_0=2\) を加算。right を進めて \(1\) に。
  • right = 1 (\(X_1=2 < 6\)): current_sum に \(P_1=3\) を加算。right を進めて \(2\) に。
  • right = 2 (\(X_2=5 < 6\)): current_sum に \(P_2=4\) を加算。right を進めて \(3\) に。
  • right = 3 (\(X_3=7 \geq 6\)): 範囲外なのでストップ。
  • 現在の合計 current_sum = 9。max_sum を \(9\) に更新。
  • left を進めるため、current_sum から \(P_0=2\) を引いて \(7\) に。

• left = 1 (\(X_1 = 2\)):

  • 許容範囲は \(2 + 5 = 7\) 未満。
  • right = 3 (\(X_3=7 \geq 7\)): 範囲外なので進めない。
  • 現在の合計 current_sum = 7。
  • left を進めるため、current_sum から \(P_1=3\) を引いて \(4\) に。

このように、right ポインタが逆戻りすることなく、常に右に進むため高速に処理できます。

計算量

• 時間計算量: \(O(N)\)
  • left と right のポインタは、それぞれ配列の端から端まで高々 \(1\) 回ずつしか移動しません。したがって、ループ全体のステップ数は高々 \(2N\) 回となり、時間計算量は \(O(N)\) で非常に高速です。Pythonでも 0.1 秒前後で余裕をもってAC（正解）できます。
• 空間計算量: \(O(N)\)
  • 植え込みの座標 \(X\) と花の本数 \(P\) を格納する配列のサイズが \(N\) に比例するため、空間計算量は \(O(N)\) です。

実装のポイント

• 高速な入出力: Pythonでは入力数 \(N\) が \(2 \times 10^5\) 程度になると、通常の input() を繰り返すだけでは入出力がボトルネックとなり TLE になることがあります。sys.stdin.read().split() を用いてすべての入力を一度にまとめて取得・分割することで、入出力を大幅に高速化しています。

• 半開区間の条件: 問題文の条件は「距離 \(D\) 未満」なので、右端の判定条件は X[right] < X[left] + D となります（<= ではなく < である点に注意してください）。

  ソースコード

import sys


def solve():
    # 入力をすべて高速に読み込む
    input_data = sys.stdin.read().split()
    if not input_data:
        return

    N = int(input_data[0])
    D = int(input_data[1])

    X = [0] * N
    P = [0] * N

    # 1次元リストから X と P を展開
    idx = 2
    for i in range(N):
        X[i] = int(input_data[idx])
        P[i] = int(input_data[idx + 1])
        idx += 2

    total_flowers = sum(P)

    # しゃくとり法を用いて、区間 [X_j, X_j + D) に含まれる花の本数の最大値を求める
    max_sum = 0
    current_sum = 0
    right = 0

    for left in range(N):
        limit = X[left] + D
        while right < N and X[right] < limit:
            current_sum += P[right]
            right += 1

        if current_sum > max_sum:
            max_sum = current_sum

        current_sum -= P[left]

    # 水やりできない花の本数の最小値を出力
    print(total_flowers - max_sum)


if __name__ == "__main__":
    solve()

---

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