概要

地球から逃げる宇宙船に追いつけるミサイルの数を求める問題。ミサイルの速度が宇宙船の速度より大きいかどうかを判定すればよい。

考察

時刻 \(t\) におけるそれぞれの位置を考えます。

• 敵の宇宙船の位置: \(D + Vt\)
• \(i\) 番目のミサイルの位置: \(S_i \cdot t\)

ミサイルが宇宙船に到達する条件は、ある \(t \geq 0\) が存在して：

\[S_i \cdot t \geq D + V \cdot t\]

これを整理すると：

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

ここで場合分けをします。

場合1: \(S_i \leq V\) のとき

左辺は \(t \geq 0\) において非正（\(\leq 0\)）です。一方、\(D \geq 1 > 0\) なので、この不等式を満たす \(t \geq 0\) は存在しません。つまり、ミサイルは宇宙船に追いつけません。

直感的にも、ミサイルの速度が宇宙船以下なら、最初に距離 \(D\) だけ離れている宇宙船に永遠に追いつけないのは明らかです。

場合2: \(S_i > V\) のとき

\(S_i - V > 0\) なので、両辺を \(S_i - V\) で割ると：

\[t \geq \frac{D}{S_i - V}\]

これは必ず正の解を持つので、十分な時間が経てばミサイルは宇宙船に追いつきます。

結論: ミサイルが宇宙船に到達できる条件は \(S_i > V\) である。

アルゴリズム

1. \(N\), \(D\), \(V\) を読み込む（\(D\) は判定条件に直接使わない）
2. 各ミサイルの速度 \(S_i\) について、\(S_i > V\) かどうかを判定する
3. 条件を満たすミサイルの個数を数えて出力する

具体例

\(N=3\), \(D=10\), \(V=5\), \(S = [3, 5, 8]\) の場合： - \(S_1 = 3 \leq 5\): 到達できない - \(S_2 = 5 \leq 5\): 到達できない（速度が同じでも初期距離があるため追いつけない） - \(S_3 = 8 > 5\): 到達できる（時刻 \(t = 10/(8-5) = 10/3\) で追いつく）

答えは \(1\)。

計算量

• 時間計算量: \(O(N)\)（各ミサイルについて定数時間の比較を行う）
• 空間計算量: \(O(1)\)（カウンタ変数のみ使用）

実装のポイント

• \(D\) の値は到達可否の判定には不要です。\(S_i > V\) かどうかだけで判定できます（\(D \geq 1\) が保証されているため）。

• \(N\) が最大 \(10^6\) と大きいので、C++ では ios::sync_with_stdio(false) と cin.tie(nullptr) で入出力を高速化しています。

• 速度の値が最大 \(10^9\) になるため、long long 型で読み込んでいます（この問題では比較のみなので int でも問題ありませんが、安全のため）。

  ソースコード

#include <iostream>
#include <vector>
using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int N;
    long long D, V;
    cin >> N >> D >> V;
    
    int count = 0;
    for(int i = 0; i < N; i++){
        long long s;
        cin >> s;
        if(s > V) count++;
    }
    
    cout << count << endl;
    return 0;
}

---

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