読者です 読者をやめる 読者になる 読者になる

algoNote

プログラミング関連

Google Code Jam 2017 Round1B A.Steed 2: Cruise Control

A問題のsmallとlargeだけ通して寝落ちしてました。。

A.Steed 2: Cruise Control

問題概要

Dashboard - Round 1B 2017 - Google Code Jam

アニーさんは馬に乗って初め地点 {0} にいて、距離 {D} の地点を目指して直線の道を進む。 道には {N} 頭の馬 {H_i} がいて、それぞれは初め地点 {K_i} にいて最高速度は {S_i} である。 各馬は前の馬に追いついたらそれ以降はその馬と同じスピードで走る。 アニーさんの乗っている馬が減速せずに一定のスピードで進む(他の馬に追いついて減速するイベントが起こらないように進む)とき 距離 {D} の地点に到達できる最短の時間を求めよ。

制約(large)

  • {1 \leq N \leq 1000}
  • {0 \lt K_i \lt D \leq 10^{9}}
  • {1 \leq S_i \leq 10000}
  • {K_i \neq K_i (i \neq j)}

考えたこと

{H_1〜H_{N-1}} はすべて {H_0} より前または同じ地点にいることが保証できるので、アニーさんは {H_0} に追いつかないギリギリのスピードで進めばいいことが分かる。

次に考えるのは {H_0} が何時間で距離 {D} に到達できるかということで、この時間を {T_{min}} とおく。するとアニーさんのスピードは {D/T_{min}} になる。( {H_0} と同時に距離 {D} の地点に到着するイメージ)

ここで時刻 {t} のときに {H_0} が距離 {D} より先にいる場合、時刻 {t} 以前に距離 {D} に到達しているはずなので {T_{min} \lt t} となる。
時刻 {t} のときに {H_0} が距離 {D} に達していない場合 {T_{min} \gt t} となる。

よって時刻 {t} のときの {H_0} の位置が分かれば {T_{min}} を二分探索で求められる。

時刻 {t} での {H_0} の位置が知りたい

時刻 {t} での各馬の位置を {x_i} とおくことにする。

{H_{N-1}} は前に馬がいないから常に {S_{N-1}}のスピードで進むことが出来る。 よって {x_{N-1} = K_{N-1} + S_{N-1} \times t}

{H_{N-2}} については {H_{N-1}} のスピード {S_{N-1}} と位置 {K_{N-1}} に依存する。

  • {H_{N-1}} に追いつかない場合
    {x_{N-2} = K_{N-2} + S_{N-2} \times t}

  • {H_{N-1}} に追いつく場合
    {x_{N-2} = x_{N-1}}

これをまとめると、 {x_{N-2} = min(K_{N-2} + S_{N-2} \times t , x_{N-1})} となる。

あとはこれをすべての馬について考えれば {x_0} が求まる。

ソースコード

二分探索のループは適当に100回回しています。