概要

一直線上に並んだ \(N\) 本の木から、長さ \(K\) 以下の区間に含まれる木の本数を最大化する問題です。ソートと二分探索を組み合わせて効率的に解きます。

考察

重要な気づき

1. 区間の端を木の位置に合わせる: 最適な区間は、必ずいずれかの木の位置を左端（または右端）とする区間になります。なぜなら、区間をずらして木を1本も含まない位置まで移動させても意味がないからです。

2. ソートの有効性: 木の座標をソートすると、区間 \([X_i, X_i + K]\) に含まれる木は連続したインデックスの範囲になります。これにより、問題は「各 \(i\) について、\(X_j \leq X_i + K\) を満たす最大の \(j\) を求める」という形に変換できます。

素朴なアプローチの問題点

全ての木のペア \((i, j)\) について \(X_j - X_i \leq K\) かどうかを調べる方法では、\(O(N^2)\) の時間がかかり、\(N = 2 \times 10^5\) の制約下ではTLE（時間超過）になります。

解決策

ソート済み配列に対して二分探索を使うことで、各木について \(O(\log N)\) で右端のインデックスを求められます。

アルゴリズム

1. 座標をソート: 木の座標 \(X\) を昇順にソートします。

2. 各木を左端として探索: \(i = 0, 1, \ldots, N-1\) について以下を行います：

   • 区間の左端を \(X_i\)、右端を \(X_i + K\) とします
   • 二分探索（bisect_right）を使って、\(X_i + K\) 以下の座標を持つ木のうち最も右にあるものの次のインデックス \(j\) を求めます
   • 区間内の木の本数は \(j - i\) 本です

3. 最大値を更新: 全ての \(i\) について木の本数の最大値を求めます。

具体例

\(N = 5\), \(K = 4\), \(X = [1, 3, 5, 8, 10]\)（ソート済み）の場合：

左端 \(X_i\)	右端 \(X_i + K\)	範囲内の木	本数
1	5	1, 3, 5	3
3	7	3, 5	2
5	9	5, 8	2
8	12	8, 10	2
10	14	10	1

よって答えは 3 です。

計算量

• 時間計算量: \(O(N \log N)\)
  • ソートに \(O(N \log N)\)
  • 各木について二分探索を行うので \(O(N \log N)\)
• 空間計算量: \(O(N)\)
  • 座標を格納する配列のサイズ

実装のポイント

• bisect_right(X, right) は「right より大きい最初の要素の位置」を返します。つまり、right 以下の要素は全てインデックス \(j - 1\) 以下に存在するため、\(j - i\) が区間内の木の本数になります。

• 左端を固定して右端を探索する方法と、右端を固定して左端を探索する方法がありますが、どちらでも同じ結果が得られます。

• 尺取り法でも \(O(N)\) で解けますが、二分探索でも十分高速です。

  ソースコード

import bisect

def solve():
    N, K = map(int, input().split())
    X = list(map(int, input().split()))
    
    # 座標をソート
    X.sort()
    
    max_count = 0
    
    # 各木を左端として、区間 [X[i], X[i] + K] 内に何本の木があるか調べる
    for i in range(N):
        left = X[i]
        right = left + K
        
        # X[i] + K 以下の最大のインデックスを二分探索で求める
        # bisect_right は right より大きい最初の位置を返すので、その1つ前までが範囲内
        j = bisect.bisect_right(X, right)
        
        count = j - i
        max_count = max(max_count, count)
    
    print(max_count)

solve()

---

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