概要

数直線上に並んだ \(N\) 個の植え込みに対し、長さ \(D\) の区間 \([s, s+D)\) をうまく選んで、その区間に含まれる花の本数を最大化する問題です。最終的な答えは「全体の花の本数 − 水やりできる花の本数の最大値」になります。

考察

まず、水やりできない花を最小化することは、水やりできる花を最大化することと同じです。全体の花の本数 \(\text{total}\) は固定なので、

\[ (\text{水やりできない花の最小値}) = \text{total} - (\text{水やりできる花の最大値}) \]

となります。よって、長さ \(D\) の窓 \([s, s+D)\) に収まる花の本数を最大化する問題に帰着します。

次に重要な観察として、スプリンクラーの設置位置 \(s\) はある植え込みの座標に合わせて考えれば十分です。なぜなら、もし区間内の一番左の植え込みが \(X_i\) なら、\(s\) を \(X_i\) より小さくしても得られる花は増えず、むしろ右側の植え込みを取りこぼす可能性が出てくるだけだからです。したがって、各植え込み \(X_i\) を区間の左端として「\(X_i \leq X_j < X_i + D\) を満たす植え込みの花の合計」を計算し、その最大値を求めればよいことになります。

素朴に各 \(i\) について毎回区間内の植え込みを数え直すと \(O(N^2)\) となり、\(N \leq 2 \times 10^5\) では間に合いません（TLE）。そこで、しゃくとり法（尺取り法 / two pointers）を使って効率化します。

アルゴリズム

座標 \(X_i\) は既に昇順にソートされて与えられている点を利用します。

左端 \(i\) を \(0\) から \(N-1\) まで動かし、それぞれに対して右端 \(j\)（区間に含まれる最後の次の位置）を管理します。ポイントは、\(i\) を右に進めるとき、条件 \(X_j < X_i + D\) の右端 \(j\) も単調に右へ移動するだけで戻らないという性質です。

具体的な手順は次の通りです。

1. 区間内の花の合計 cur と、最大値 best を用意する。
2. 左端 \(i\) を \(0\) から増やしていく。
3. 右端 \(j\) を、\(X_j < X_i + D\) を満たす限り右へ進め、進めるたびに \(P_j\) を cur に加える。
4. このとき cur が窓 \([X_i, X_i + D)\) に含まれる花の合計なので、best を更新する。
5. 次の左端へ進む前に、左端の植え込みの花 \(P_i\) を cur から引いておく。

こうすることで、\(i\) と \(j\) がそれぞれ一方向に進むだけなので、各植え込みは加算・減算をそれぞれ高々1回ずつしか行いません。

最後に total - best を出力します。

簡単な例

例えば \(D = 5\) で植え込みが座標 \(1, 3, 6, 8\) にあるとします。 - 左端を \(X=1\) にすると区間は \([1, 6)\) で、座標 \(1, 3\) が含まれます。 - 左端を \(X=3\) にすると区間は \([3, 8)\) で、座標 \(3, 6\) が含まれます。 - 左端を \(X=6\) にすると区間は \([6, 11)\) で、座標 \(6, 8\) が含まれます。

このように左端を進めると右端も右へ移動していくため、しゃくとり法がそのまま適用できます。

計算量

• 時間計算量: \(O(N)\)（入力の読み込み・ソート不要部分を含めても線形。\(i, j\) がそれぞれ高々 \(N\) 回しか進まない）
• 空間計算量: \(O(N)\)（座標と花の本数を格納する配列）

実装のポイント

• 区間は \(s + D\) を「未満」で扱う点に注意します。条件は \(X_j < X_i + D\) であり、\(\leq\) ではありません。コードでも X[j] < X[i] + D と厳密な不等号を使っています。

• 値が大きい（花の合計が最大で \(2 \times 10^5 \times 10^9 = 2 \times 10^{14}\) 程度）ため、64bit整数の範囲を意識する必要があります。Python では整数が多倍長なので気にする必要はありませんが、他言語では long long を使うべきです。

• 入力が大きいので、sys.stdin.buffer.read() で一括読み込みすると高速です。

• cur -= P[i] を各ループの末尾で行うことで、次のループでは左端が一つ右へずれた状態の合計を保てます。右端 \(j\) は引き続き同じ位置から再開できるため、無駄な再計算が発生しません。

  ソースコード

import sys

def main():
    data = sys.stdin.buffer.read().split()
    idx = 0
    N = int(data[idx]); idx += 1
    D = int(data[idx]); idx += 1
    X = [0]*N
    P = [0]*N
    for i in range(N):
        X[i] = int(data[idx]); idx += 1
        P[i] = int(data[idx]); idx += 1
    
    total = sum(P)
    
    best = 0
    cur = 0
    j = 0
    for i in range(N):
        if j < i:
            j = i
            cur = 0
        # ensure j covers from X[i]
        # remove? not needed since left moves forward
        while j < N and X[j] < X[i] + D:
            cur += P[j]
            j += 1
        if cur > best:
            best = cur
        cur -= P[i]
    
    print(total - best)

main()

---

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