公式

A - 宇宙船を迎え撃て / Intercept the Spaceship 解説 by MMNMM

初心者の方へ

この問題は、for 文などを用いて \(S _ 1,S _ 2,\ldots,S _ N\) に対して判定問題を解き、条件を満たすミサイルの個数を求めることで解くことができます。

速度 \(S _ i\) のミサイルが敵の宇宙船に到達できる必要十分条件は、\(S _ i\gt V\) です。

証明

ミサイルが敵の宇宙船に到達することは、ある時刻 \(t\ (0\le t)\) が存在して時刻 \(t\) にミサイルの座標が宇宙船の座標以上になっていることでした。 これを数式に直すと \(tS _ i\ge tV+D\) となります。 これを整理すると \(t(S _ i-V)\ge D\) です。 制約より \(D\ge1\) なので、特に \(t(S _ i-V)\gt0\) となります。 \(t\ge0\) より、\(S _ i-V\gt0\) が必要です。

逆に、\(S _ i\gt V\) なら \(t=\dfrac D{S _ i-V}\gt 0\) が条件を満たします。

よって、速度 \(S _ i\) のミサイルが敵の宇宙船に到達できる必要十分条件が \(S _ i\gt V\) であることが示されました。

あとは、for 文などを用いて \(S _ i\gt V\) を満たす \(i\) がいくつあるか数えればよいです。

実装例は以下のようになります。

#include <iostream>
using namespace std;

int main() {
    int N, D, V;
    cin >> N >> D >> V;

    int ans = 0;
    for (int i = 0; i < N; ++i) {
        int S;
        cin >> S;
        if (S > V) { // 宇宙船に追いつけるなら
            ++ans; // 答えを増やす
        }
    }

    cout << ans << endl;
    return 0;
}

N, D, V = map(int, input().split())

# S > V を満たすものの個数を求める
print(len([S for S in map(int, input().split()) if S > V]))

投稿日時:
最終更新: