問題概要

一直線上に $N$ 個の点がある。点 $i$ の座標は $A_{i}$ である。

この直線上で幅 $M$ の区間を配置する。左端の座標を $x$ とするとき、 $x \le A_{i} \lt x + M$ を満たす $i$ の個数をスコアとする。最大スコアを求めよ。

制約

$1 \le N \le 3 \times 10^{5}$
$M, A_{i} \le 10^{9}$

考えたこと

まず重要な考察として

幅 $M$ の区間を置くとき、その左端がある点に一致する場合のみを考えればよい

というのがある。なぜなら、そうでない場合を考えたとき、区間を右へと移動させても、区間の覆う点が減少することはないからだ (むしろ増えるかもしれない)。そして、右側に移動していって、左端に点が重なる瞬間まで右側に移動できる。

以上の考察から、区間の左端が点に一致する場合のみ考えれば良い。

各点に対して

簡単のため、 $A$ をソートしよう。このとき、問題は次のようになる。

各 $i$ に対して、

$A_{i} \le A_{j} \lt A_{i} + M$

を満たすような $j$ の個数を求めよ (その最大値が答えとなる)。

これは、次の手順で求められる。

$A_{k} \ge A_{i} + M$ となる最小の $k$ を求める (lower_bound() によって、計算量 $O(\log N)$ で求められる)
$k - i$ が答え

全体の計算量は $O(N \log N)$ となる。

コード

#include <bits/stdc++.h>
using namespace std;

int main() {
    long long N, M;
    cin >> N >> M;
    
    vector<long long> A(N);
    for (int i = 0; i < N; ++i) cin >> A[i];
    sort(A.begin(), A.end());
    
    int res = 0;
    for (int i = 0; i < N; ++i) {
        long long x = A[i];
        int it = lower_bound(A.begin(), A.end(), x + M) - A.begin();
        res = max(res, it - i);
    }
    cout << res << endl;
}