概要

高橋君の「最短到着時間」を数式で求め、終電の駅到着時刻と比較するだけで Yes/No を判定する問題です。

考察

重要な気づき

高橋君は速度が - 通常：\(1\) - ダッシュ中：\(D\)

で、ダッシュできる合計時間が \(K\) 秒です。

ある時刻 \(t\) 秒までにダッシュした総時間を \(x\) 秒（\(0 \le x \le \min(K,t)\)）とすると、高橋君が進める距離は

\[ ( t-x )\cdot 1 + x \cdot D = t + (D-1)x \]

となります。
距離を最大化したいので、可能な限り \(x\) を大きくする（＝ダッシュを使えるだけ使う）のが最適です。
つまり、「いつダッシュするか」ではなく 「合計で何秒ダッシュするか」だけが効くため、最短到着時間は数式で一意に決まります。

素朴な方法がダメな理由

「毎秒ダッシュするか選んでシミュレーション」すると、最悪で \(10^9\) 秒以上の操作になり得て間に合いません（TLE）。

そこで、最短到着時間を場合分けで直接計算します。

終電側

終電は座標 \(M\) から駅 \(G\) へ向かうので、駅までの距離は

\[ \text{dist\_train} = M-G \]

終電の駅到着時刻は

\[ T_{\text{train}} = \frac{M-G}{V} \]

です。高橋君が駅に着く時刻 \(T_{\text{taka}}\) がこれ以下なら乗れます（同時到着も可）。

アルゴリズム

高橋君の最短到着時間 \(T_{\text{taka}}\) を求めます。

1) ダッシュだけで駅に届く場合：\(D K \ge G\)

ダッシュ中（\(t \le K\)）は距離が \(Dt\) なので、

\[ Dt \ge G \Rightarrow t \ge \frac{G}{D} \]

よって

\[ T_{\text{taka}} = \frac{G}{D} \]

判定は $\( \frac{G}{D} \le \frac{M-G}{V} \)$

ですが、小数を使わずに両辺を掛け算して

\[ G \cdot V \le D \cdot (M-G) \]

で判定します。

2) ダッシュを \(K\) 秒使っても届かない場合：\(D K < G\)

まず \(K\) 秒ダッシュして進める距離は \(DK\)。残りは通常速度 \(1\) で進むのが最適です。

このとき、合計時間 \(t\)（\(t \ge K\)）で進める最大距離は

\[ t + (D-1)K \]

駅に届く条件は

\[ t + (D-1)K \ge G \Rightarrow t \ge G - (D-1)K \]

ここで \(DK < G\) なら \(G-(D-1)K > K\) が成り立つため、最短時間はそのまま

\[ T_{\text{taka}} = G - (D-1)K \]

判定は

\[ G - (D-1)K \le \frac{M-G}{V} \]

小数を避けて

\[ \left(G-(D-1)K\right)\cdot V \le (M-G) \]

で判定します。

以上により、定数時間で Yes/No を出せます。

計算量

• 時間計算量: \(O(1)\)
• 空間計算量: \(O(1)\)

実装のポイント

• 浮動小数（float）を使わず、クロス積で比較します（誤差防止）。

  • 例：\(\frac{a}{b}\le\frac{c}{d}\) を \(a d \le b c\) にする。

• 値が大きい（最大で \(10^{15}\) やその積）ので、Python 以外の言語では 64bit を超える可能性に注意し、必要なら 128bit 整数を使います。

• 分岐条件は D*K >= G（ダッシュだけで届くか）で決まります。K=0 のときも自然に処理できます。

  ソースコード

import sys

def main():
    G, M, D, K, V = map(int, sys.stdin.readline().split())

    dist_train = M - G  # distance for the train to reach the station

    if D * K >= G:
        # Takahashi can reach in time G/D
        ok = (G * V) <= (D * dist_train)
    else:
        # Use all K seconds of dash, then normal speed
        t_min = G - (D - 1) * K  # = K + (G - D*K)
        ok = (t_min * V) <= dist_train

    print("Yes" if ok else "No")

if __name__ == "__main__":
    main()

---

この解説は gpt-5.2-high によって生成されました。