概要

この問題は、地球から遠ざかる敵の宇宙船に、用意された \(N\) 機のミサイルのうち何機が追いつけるかを判定する問題です。 数式を整理することで、複雑なシミュレーションを行うことなく、ミサイルと宇宙船の「速度の比較」だけで解くことができます。

考察

まず、ミサイルが宇宙船に追いつく条件を数式で表してみましょう。

時刻 \(t \ (t \geq 0)\) における、敵の宇宙船と \(i\) 番目のミサイルの座標はそれぞれ以下のようになります。 - 宇宙船の座標: \(D + Vt\) - ミサイルの座標: \(S_i t\)

ミサイルが宇宙船に到達できるとは、ある時刻 \(t \geq 0\) において、ミサイルの座標が宇宙船の座標以上になることです。つまり、次の不等式を満たす \(t \geq 0\) が存在するかどうかを判定します。

\[S_i t \geq D + Vt\]

この不等式を \(t\) について整理するために、 \(Vt\) を左辺に移項します。

\[(S_i - V) t \geq D\]

ここで、問題の制約から宇宙船の初期位置 \(D\) は \(1\) 以上（ \(D \geq 1\) ）であることが分かっています。このことを踏まえて、ミサイルの速度 \(S_i\) と宇宙船の速度 \(V\) の大小関係で場合分けをします。

1. \(S_i \leq V\) のとき（ミサイルが宇宙船と同じか、それより遅い場合）

   • \(S_i - V \leq 0\) となります。
   • \(t \geq 0\) なので、左辺の \((S_i - V) t\) は常に \(0\) 以下になります。
   • 右辺は \(D \geq 1\) なので、不等式 \((S_i - V) t \geq D\) を満たすような \(t \geq 0\) は絶対に存在しません。
   • つまり、追いつくことはできません。

2. \(S_i > V\) のとき（ミサイルが宇宙船より速い場合）

   • \(S_i - V > 0\) となります。
   • 時間 \(t\) を十分に大きく（具体的には \(t \geq \frac{D}{S_i - V}\) に）すれば、必ず不等式を満たすことができます。
   • つまり、いつかは必ず追いつくことができます。

以上の考察から、初期位置 \(D\) の値に関わらず、「ミサイルの速度 \(S_i\) が宇宙船の速度 \(V\) よりも大きいこと（ \(S_i > V\) ）」が、ミサイルが宇宙船に到達できるための必要十分条件であることが分かります。

アルゴリズム

1. 入力から宇宙船の速度 \(V\) と、各ミサイルの速度 \(S_i \ (1 \leq i \leq N)\) を取得します。
2. 各 \(S_i\) について、 \(S_i > V\) であるかを判定します。
3. 条件を満たすミサイルの個数をカウントし、最終的な答えとして出力します。

宇宙船の初期位置 \(D\) は判定に影響しないため、無視して構いません。

計算量

• 時間計算量: \(O(N)\) \(N\) 個のミサイルの速度 \(S_i\) について、それぞれ \(V\) との大小比較を \(1\) 回ずつ行うため、ミサイルの数 \(N\) に比例した時間で処理が完了します。\(N \leq 10^6\) であるため、実行時間制限に余裕で間に合います。
• 空間計算量: \(O(N)\) すべての入力をメモリ上に読み込むため、ミサイルの数 \(N\) に比例したメモリを使用します。

実装のポイント

• 高速な入出力: この問題では \(N\) が最大で \(10^6\) と非常に大きいため、Pythonで input() を用いて \(1\) 行ずつ読み込むと、入出力のオーバーヘッドにより実行時間制限（TLE）になってしまう可能性があります。 sys.stdin.read().split() を使用することで、すべての入力を一度にまとめて高速に読み込むことができます。

  ソースコード

import sys

def main():
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    V = int(input_data[2])
    
    count = 0
    for x in input_data[3:]:
        if int(x) > V:
            count += 1
            
    print(count)

if __name__ == '__main__':
    main()

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