概要

ボールの重さに比例して飛ぶ距離が決まる的当てゲームにおいて、各ボールが的の範囲内に落ちるかどうかを判定し、当たるボールの数を求める問題です。

考察

問題の本質は、各ボールの重さ \(D_i\) が的の範囲 \([L-W, L+W]\) 内に含まれるかどうかを判定することです。制約条件から \(N\) は最大20万個まであり得るため、各ボールについて単純に条件判定を行うだけで十分効率的です。条件式は \(L - W \leq D_i \leq L + W\) とシンプルで、各ボールに対して定数時間で判定可能です。

アルゴリズム

1. 入力値 \(N\), \(L\), \(W\) およびボールの重さのリスト \(D_list\) を読み込む
2. カウンタ変数 count を0で初期化する
3. 各ボールの重さ \(D_i\) について、以下の条件を満たすかチェックする:
   • \(L - W \leq D_i \leq L + W\)
4. 条件を満たす場合、カウンタを1増やす
5. 最終的なカウンタの値を出力する

計算量

• 時間計算量: \(O(N)\)
  • 各ボールに対して1回の比較を行うため
• 空間計算量: \(O(N)\)
  • ボールの重さを格納するリストのサイズが \(N\) のため

実装のポイント

• 条件式を書く際に、不等号の向きに注意する必要があります

• 入力値がすべて整数であるため、浮動小数点数の誤差を気にする必要がありません

• ボールの重さがすべて異なりますが、この問題では特に影響しません

  ソースコード

def main():
    import sys
    data = sys.stdin.read().split()
    n = int(data[0])
    L = int(data[1])
    W = int(data[2])
    D_list = list(map(int, data[3:3+n]))
    
    count = 0
    for D in D_list:
        if L - W <= D <= L + W:
            count += 1
            
    print(count)

if __name__ == "__main__":
    main()

この解説は deepseekv3 によって生成されました。