概要

木の位置が与えられたとき、長さが \(K\) 以下の区間 \([L,R]\) を1つ選んで、その中に入る木の本数の最大値を求める問題です。

考察

• ある区間 \([L,R]\) に入る木の本数は、座標を昇順に並べたとき「連続する部分（連続した添字の範囲）」として数えられます。
  つまり、座標をソートして \(X[0] < X[1] < \dots < X[N-1]\) とすると、区間内に入る最大本数は「ある \(l,r\) を選んで \(X[r]-X[l]\le K\) を満たす範囲の最大長」に一致します。
• 素朴には、全ての \(l\) について条件を満たす最大の \(r\) を探す（あるいは全区間を試す）と \(O(N^2)\) になり、\(N \le 2\times 10^5\) では間に合いません。
• 重要な気づきは、「右端 \(r\) を右に動かしていくと、条件 \(X[r]-X[l]\le K\) を満たすための左端 \(l\) は右にしか動かない」ことです。
  これにより、左右の端をそれぞれ一方向に動かす しゃくとり法（Two Pointers） で全体を \(O(N)\) で処理できます。

例：\(X=[1,3,4,10,11]\), \(K=3\)
- \(r=2\)（座標4）までなら、\([1,4]\) の長さは3で3本入る
- \(r=3\)（座標10）にすると \(10-1=9>3\) なので左端を動かして条件を満たすまで詰める
この「左端が戻らない」性質が高速化の鍵です。

アルゴリズム

1. 座標配列 \(X\) を昇順にソートする。
2. 左端ポインタ \(l=0\)、答え \(ans=0\) を用意する。
3. 右端ポインタ \(r\) を \(0\) から \(N-1\) まで順に動かす：
   • 条件 \(X[r]-X[l] \le K\) を満たすまで、\(X[r]-X[l] > K\) の間は \(l\) を \(1\) ずつ増やす。
   • このとき区間内の本数は \(r-l+1\) なので、\(ans=\max(ans, r-l+1)\) で更新する。
4. \(ans\) を出力する。

ソート後は「\(X[r]-X[l]\le K\) を満たす最大の連続区間の長さ」を求めていることになります。

計算量

• 時間計算量: ソートが \(O(N\log N)\)、しゃくとり法が \(O(N)\) なので全体で \(O(N\log N)\)
• 空間計算量: 座標配列などで \(O(N)\)

実装のポイント

• まずソートしないと「区間に入る木」が連続部分として扱えず、しゃくとり法が使えません。

• while X[r] - X[l] > K: l += 1 のように、条件を満たすまで左端を進めます（戻さないのがポイント）。

• 答えの更新は各 \(r\) で r - l + 1 を計算するだけです。

  ソースコード

import sys

def main():
    input = sys.stdin.readline
    N, K = map(int, input().split())
    X = list(map(int, input().split()))
    X.sort()

    ans = 0
    l = 0
    for r in range(N):
        while X[r] - X[l] > K:
            l += 1
        ans = max(ans, r - l + 1)

    print(ans)

if __name__ == "__main__":
    main()

この解説は gpt-5.2-high によって生成されました。