概要

\(N\) 個のボールがあり、それぞれの重さ \(D_i\) がそのまま飛距離となります。飛距離が \(L-W\) 以上 \(L+W\) 以下の範囲に収まるボールがいくつあるかを求める問題です。

考察

この問題で最も重要なのは、「ボールが的に当たる条件」を数式で整理することです。

問題文から、重さ \(D_i\) のボールが的に当たるための条件は以下の通りです： - 高橋君からの距離が \(L-W\) 以上 - 高橋君からの距離が \(L+W\) 以下

これを一つの不等式にまとめると、 \(L-W \leq D_i \leq L+W\) となります。

各ボールの判定は独立して行えるため、すべてのボールに対してこの不等式が成り立つかどうかを順番にチェックしていけば正解を得ることができます。

制約を確認すると、ボールの数 \(N\) は最大で \(2 \times 10^5\) です。1つずつのボールを判定する素朴なアプローチ（\(O(N)\)）をとれば、計算回数は \(2 \times 10^5\) 回程度となり、実行時間制限内に十分に間に合います。

アルゴリズム

以下の手順で解を求めます。

1. 的に当たる範囲の下限 \(L-W\) と上限 \(L+W\) を計算し、変数（lower_bound, upper_bound）に格納する。
2. 当たったボールの数をカウントする変数 count を \(0\) で初期化する。
3. 各ボールの重さ \(D_i\) について、以下の処理を繰り返す：
   • もし \(lower\_bound \leq D_i\) かつ \(D_i \leq upper\_bound\) ならば、 count に \(1\) を加える。
4. 最終的な count の値を出力する。

計算量

• 時間計算量: \(O(N)\)
  • \(N\) 個のボールをそれぞれ 1 回ずつ確認するため、 \(N\) に比例した時間がかかります。
• 空間計算量: \(O(N)\)
  • 入力された \(N\) 個の重さをリストとして保持する場合、 \(N\) に比例したメモリを使用します。

実装のポイント

• 高速な入出力: \(N\) が \(2 \times 10^5\) と比較的大きいため、Pythonでは input() を繰り返すよりも sys.stdin.read().split() などを使って一括で入力を読み込む方が実行時間を短縮できます。

• 範囲判定の書き方: Pythonでは lower_bound <= d <= upper_bound のように、数学の不等式に近い形で直感的に範囲判定を記述できます。

  ソースコード

import sys

def solve():
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    n = int(input_data[0])
    l = int(input_data[1])
    w = int(input_data[2])
    d_list = input_data[3:]
    
    lower_bound = l - w
    upper_bound = l + w
    
    count = 0
    for i in range(n):
        d = int(d_list[i])
        if lower_bound <= d <= upper_bound:
            count += 1
            
    print(count)

if __name__ == '__main__':
    solve()

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