概要

各ボールは重さ \(D_i\) だけ飛ぶので、距離が的の範囲 \([L-W,\, L+W]\) に入るボールの個数を数える問題です。

考察

• ボールの重さ \(D\) のボールを投げると「ちょうど距離 \(D\)」だけ飛ぶとあるため、ボールが落ちる位置＝重さとみなせます。
• 的に当たる条件は「落ちた距離が \(L-W\) 以上 \(L+W\) 以下」なので、各 \(D_i\) について
  • \(L-W \le D_i \le L+W\) を満たすかどうかを判定すればよいです。
• \(N \le 2\times 10^5\) なので、全てのボールを1回ずつチェックする素朴な全探索 \(O(N)\) で十分間に合います。
• 逆に、無理にソートして二分探索する方法も可能ですが（\(O(N\log N)\)）、今回は不要です。条件判定だけで答えが出ます。

例：

• \(L=10,\ W=2\) のとき的の範囲は \([8,12]\)
• \(D=[3,8,10,13,12]\) なら、当たるのは \(8,10,12\) の3個です。

アルゴリズム

1. 的に当たる距離の下限 \(low = L-W\)、上限 \(high = L+W\) を計算する。
2. 各ボールの重さ \(D_i\) について、\(low \le D_i \le high\) を満たすならカウントする。
3. カウントを出力する。

計算量

• 時間計算量: \(O(N)\)（各 \(D_i\) を1回ずつ判定）
• 空間計算量: \(O(1)\)（入力配列を除く追加領域）

実装のポイント

• 判定は 両端を含む（「以上」「以下」）なので、条件は low <= x <= high とします。

• \(L, W, D_i\) は最大 \(10^9\) ですが、Python の整数ならオーバーフローを気にせず扱えます。

• 入力が大きいので sys.stdin.readline を使うと安全です。

  ソースコード

import sys

def main():
    input = sys.stdin.readline
    N, L, W = map(int, input().split())
    D = list(map(int, input().split()))
    low = L - W
    high = L + W
    ans = sum(1 for x in D if low <= x <= high)
    print(ans)

if __name__ == "__main__":
    main()

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