概要

ボールを投げて的に当たる個数を数える問題。ボールの重さが飛距離に対応し、的に当たる条件は飛距離が \([L - W, L + W]\) の範囲内であるかどうか。

考察

この問題では、各ボールの重さ \(D_i\) がそのまま飛距離となるため、的に当たる条件は次の不等式で表せる：

\[ L - W \leq D_i \leq L + W \]

つまり、ボールの重さがこの範囲に含まれているかどうかを判定すればよい。

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

最も簡単な方法は、すべてのボールについてこの不等式をチェックすることである。しかし、制約より \(N\) は最大で \(2 \times 10^5\) あるため、毎回全探索すると最悪時間計算量が \(O(N)\) となり、間に合わない可能性がある（特にPythonなど遅い言語では）。

改善策：ソート＋二分探索

そこで、ボールの重さをあらかじめソートしておけば、範囲 \([L - W, L + W]\) に含まれるボールの個数を高速に求めることができる。これは、二分探索を使うことで実現できる。

• bisect_left(D, left)：配列の中で left 以上の最小のインデックス
• bisect_right(D, right)：配列の中で right より大きい最小のインデックス

この2つの差が、まさに条件を満たすボールの個数となる。

具体例

例えば以下のような入力があったとする：

N=5, L=10, W=3
D = [7, 9, 10, 12, 15]

的の範囲は \([10 - 3, 10 + 3] = [7, 13]\)。

ソート後の \(D = [7, 9, 10, 12, 15]\) に対して、 - bisect_left(D, 7) → 0 - bisect_right(D, 13) → 4

よって、範囲内のボールの数は \(4 - 0 = 4\) 個となる。

アルゴリズム

1. 入力を読み込む。
2. ボールの重さリスト \(D\) を昇順にソートする。
3. 的の範囲 \([L - W, L + W]\) を計算する。
4. bisect_left と bisect_right を使って、範囲内にあるボールの個数を求める。
5. 結果を出力する。

計算量

• 時間計算量: \(O(N \log N)\) （ソートに dominate）
• 空間計算量: \(O(1)\) （追加の大きなメモリを使わない）

実装のポイント

• Python では bisect モジュールを使うことで簡単に二分探索が可能。

• bisect_left は「以上」、bisect_right は「より大きい」境界を探すので注意。

• 入力の順序は問われないので、ソートしても問題ない。

  ソースコード

import bisect

N, L, W = map(int, input().split())
D = list(map(int, input().split()))

# 的の範囲 [L - W, L + W]
left = L - W
right = L + W

# ボールの重さをソート
D.sort()

# 的に入る範囲に含まれるボールの数を二分探索で求める
# 重さ D が left 以上 right 以下のものを数える
low_index = bisect.bisect_left(D, left)
high_index = bisect.bisect_right(D, right)

print(high_index - low_index)

---

この解説は qwen3-coder-480b によって生成されました。