概要

直線上に並んだ \(N\) 本のりんごの木のうち、長さ \(K\) 以下の区間に含まれる木の最大本数を求める問題です。

考察

この問題を解くための重要なポイントは以下の3点です。

1. 座標のソート: 与えられる木の座標 \(X_i\) はバラバラな順序で与えられます。区間内にある木を効率よく数えるためには、まず座標を昇順（小さい順）に並べ替えるのが定石です。ソートすることで、「連続する番号の木が、同じ区間に含まれる」という性質を利用できるようになります。

2. 最適な区間のとり方: 「長さ \(K\) 以下の区間」は無限に考えられますが、最適な区間の左端 \(L\) は、必ずいずれかのりんごの木の座標 \(X_i\) と一致させて良いことがわかります。なぜなら、中途半端な位置から区間を始めても、左側にずらして木に合わせることで、損をすることはないからです。

3. 素朴な方法の限界: 全ての木 \(i\) について、「木 \(i\) を左端としたときに、右端 \(X_i + K\) までに何本の木があるか」を数える方法を考えます。

   • 各木に対して、他の全ての木をチェックすると \(O(N^2)\) の時間がかかります。
   • 今回 \(N = 2 \times 10^5\) なので、\(N^2 = 4 \times 10^{10}\) となり、制限時間内に終わりません。 そこで、より効率的なしゃくとり法（または二分探索）が必要になります。

アルゴリズム

ソート済みの座標に対して、しゃくとり法（Two Pointers）を適用します。

1. 木の座標 \(X\) を昇順にソートします。
2. 区間の左端を指すポインタ left と、右端を指すポインタ right を用意します。
3. right を \(0\) から \(N-1\) まで 1 つずつ進めながら、以下の操作を行います：
   • 現在の区間の長さ X[right] - X[left] が \(K\) を超えている間、left を右に進めます。
   • 長さが \(K\) 以下になったら、その区間に含まれる木の数 right - left + 1 を計算します。
   • これまでの最大本数を更新します。

この方法では、left と right がそれぞれ一度ずつしか配列を走査しないため、非常に高速に動作します。

計算量

• 時間計算量: \(O(N \log N)\)
  • 座標のソートに \(O(N \log N)\) かかります。
  • しゃくとり法の部分は \(O(N)\) です。
  • 全体としてソートが支配的となり、\(O(N \log N)\) となります。
• 空間計算量: \(O(N)\)
  • 木の座標を保持するための配列に \(O(N)\) のメモリを使用します。

実装のポイント

• ソートを忘れない: 入力された座標は順不同であるため、必ず最初に sort() を行う必要があります。

• 区間の長さの判定: 問題文の「区間の長さが \(K\) 以下」とは、右端の座標を \(R\)、左端を \(L\) としたとき \(R - L \leq K\) を満たすことを指します。コード上では x[right] - x[left] > k の間、left を進めることでこの条件を維持しています。

• 大量の入力: \(N\) が大きいため、Python の場合は sys.stdin.read().split() などを用いて高速に入力を読み込むのが望ましいです。

  ソースコード

import sys

def main():
    # 入力を標準入力からすべて読み込む
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # N: りんごの木の本数, K: 区間の最大長
    n = int(input_data[0])
    k = int(input_data[1])
    
    # x: 各りんごの木の座標
    x = list(map(int, input_data[2:]))
    
    # 座標を昇順にソートする
    x.sort()
    
    max_trees = 0
    left = 0
    
    # しゃくとり法（Two Pointers）を用いて、
    # x[right] - x[left] <= k を満たす最大の個数 (right - left + 1) を求める
    for right in range(n):
        # 区間の長さが K を超える間、左端のポインタを進める
        while x[right] - x[left] > k:
            left += 1
        
        # 現在の区間内に含まれる木の数
        current_trees = right - left + 1
        
        # 最大値を更新
        if current_trees > max_trees:
            max_trees = current_trees
            
    # 結果を出力
    print(max_trees)

if __name__ == "__main__":
    main()

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