概要

\(N\) 個のボールそれぞれについて、飛ぶ距離（＝重さ \(D_i\)）が的の範囲 \([L-W, L+W]\) に収まるかどうかを判定し、当たるボールの個数を数える問題です。

考察

重要な気づき

ボールの重さが \(D\) のとき、ボールはちょうど距離 \(D\) だけ飛びます。的に当たる条件は、ボールが落ちる位置（＝距離 \(D\)）が \(L - W\) 以上 \(L + W\) 以下であることです。

つまり、各ボールについて次の不等式が成り立つかを確認するだけです：

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

具体例

例えば \(L = 10\), \(W = 3\) の場合、的の範囲は \([7, 13]\) です。

• 重さ \(5\) のボール → 距離 \(5\) に落ちる → 範囲外 → 外れ
• 重さ \(8\) のボール → 距離 \(8\) に落ちる → 範囲内 → 当たり
• 重さ \(13\) のボール → 距離 \(13\) に落ちる → 範囲内 → 当たり
• 重さ \(14\) のボール → 距離 \(14\) に落ちる → 範囲外 → 外れ

アプローチについて

この問題は各ボールを1つずつ確認すれば十分です。\(N\) が最大 \(2 \times 10^5\) なので、全ボールを1回ずつ走査する \(O(N)\) の方法で余裕を持って間に合います。ソートや二分探索などの工夫は不要です。

アルゴリズム

1. 的の範囲の下限 \(lo = L - W\) と上限 \(hi = L + W\) を計算する。
2. \(N\) 個のボールそれぞれについて、重さ \(D_i\) が \(lo \leq D_i \leq hi\) を満たすかを判定する。
3. 条件を満たすボールの個数を数えて出力する。

N, L, W = map(int, input().split())
D = list(map(int, input().split()))
lo = L - W
hi = L + W
print(sum(1 for d in D if lo <= d <= hi))

計算量

• 時間計算量: \(O(N)\) — 各ボールについて定数時間の比較を1回行うだけ
• 空間計算量: \(O(N)\) — ボールの重さを格納するリスト分

実装のポイント

• Python では lo <= d <= hi と書くことで、数学的な区間の判定をそのまま表現できます。これは lo <= d and d <= hi と同じ意味です。

• 制約より \(W \leq L\) が保証されているため、\(L - W \geq 0\) となり、下限が負になる心配はありません。

• sum(1 for d in D if 条件) というジェネレータ式を使うことで、条件を満たす要素の個数を簡潔にカウントできます。

  ソースコード

N, L, W = map(int, input().split())
D = list(map(int, input().split()))
lo = L - W
hi = L + W
print(sum(1 for d in D if lo <= d <= hi))

---

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