きままにものづくり

日々の気付いたことなんかを書いてます。

POJ 2674 : Linear World

問題

一直線上に左右それぞれに進行する物体がある。直線の長さLと物体の速度Vと初期位置Pと進行方向が与えられる。最後に落ちる物体の名称と時間を求めよ。

解法

貪欲法を使う。衝突により方向は変わるが速度は変わらない。注目物体以外に何もないと仮定し、その条件下で最大の生存時間が最後に落ちる物体の時間になる。最大生存時間を有する物体の進行方向にある全ての物体の中で、進行方向が逆な物体の数を数える。その数だけ進行方向にシフトさせれば最後に落ちる物体の名称が求まる。
最大生存時間は切り捨てて表示させることに注意する。

計算法

 O(N)
N:物体の数

コード