2012年5月17日木曜日

GCJ2012 Round 1C Problem B. 解き方

Google Code Jam 2012 Round 1C
Problem B. Out of Gas 解き方

実践したソースは このあたり にあります。
問題紹介は こちら です。

以下ネタバレ

横軸に経過時間、縦軸に移動距離を取ったグラフをイメージすると考えやすいです。
時間の経過と自車の動き:
時間の経過と前走車の動き例:

最初に自車が山頂からノーブレーキで家まで移動する時間を求めておきます。ヒントの数式から
D = v0 * t + 0.5 * a * t2
山頂で静止した状態からスタートするので初速度 v0 = 0 で、
t = sqrt(D * 2 / a)
となります。(sqrt()は平方根を返す関数とします)

前走車より早く家(グラフの一番上)に着くことはないので、最速のケースで、前走車(グラフ赤線)と自車(グラフ青線)が同時に家に着くことになります。

このとき、スタートより早く出発することはできないので、先ほどのノーブレーキで家まで移動する時間の方が長ければそちらに合わせます。

グラフの横軸(経過時間)で見て、どのタイミングでも前走車が先行している(つまり赤線が青線の上にある)必要があります。Sample #3 の前走車ように、最初はゆっくりで、その後急に速度が上がる場合、自車の方が先行してしまうことがあります(図の薄い線)。
前走車の赤線グラフは右肩上がり(バックしない)なので、速度が変わるタイミングごとに自車の方が前(青線グラフが上)にいないか確認します。自車の方が先行している場合は、このタイミングで前走車と同じ場所に来るように自車の出発時間を調整します(図の青線のようにグラフを右にスライド)。
出発時間を n とすると
xi = 0.5 * a * (ti - n)2
が成り立つように
n = ti - sqrt(xi * 2 / a)
と出発時間 n を求めます。

これを全ての速度が変わるタイミングでチェックすれば「最短で家に着く時間」を求められます。出発時間より早い速度変化点は無視できます。

出発時間を調整するだけで、途中でブレーキを使う必要はない。というのがポイントのように思います。グラフを描くとわかりやすいですね。

0 件のコメント:

コメントを投稿