GCJ2012 Round 1C Problem B. 問題紹介

Google Code Jam 2012 Round 1C
Problem B. Out of Gas 問題紹介

車のガソリンが無くなってしまったけれど、幸運なことに今は丘の上にいるので、坂を下ってふもとの家までなるべく早く帰り着きたい… という無茶苦茶な設定のお話w
ただし丘の途中に車（前走車）がいて追い抜くことはできません。ブレーキを使って減速することはできます。

スタート時、自車は山頂 0m地点にいて静止しています（0m/s）。その後等加速度（a m/s²）で動いていきます。初速度を v0 とした場合、t 秒後の位置は

v0 * t + 0.5 * a * t²

で求められる、、というヒントがあります。

前走車はスタートから ti 秒後に山頂から xi mの地点にいます。ti 秒から ti+1 秒の間は等速で xi mから xi+1 mまで移動します。（ti 秒のところで前走車の速度が変わります）
自車も前走車もその大きさは無視できて、「点」と考えることができます。自車は前走車を追い抜くことはできませんが、ピッタリ後ろにいる場合、前走車と同時に自車も家に着くことができます。（前走車より早く家に着くことはありません）

入力データ:
最初の行は問題数 T。以降 T問の問題データが続きます。
問題データの最初の行には、家までの距離 D、前走車の位置情報の数 N、加速度のパターン数 A がスペース区切りで書かれています。
その後 N行、前走車の位置情報（スタートからの時間 ti とその時点の山頂からの距離 xi）があります。
最後の行には A個の加速度が書かれています。各加速度の場合、最も早く家に着くのはスタートから何秒後か、を求めます。（回答はA個の時間を答えることになります）

データ制限:

• 1 ≤ T ≤ 20 （問題数20問。ただし各問でA個の加速度ごとの時間を求めます）
• 1.0 ≤ D ≤ 10⁴ （家までの距離は最大10,000m）
• Small input の場合：1 ≤ N ≤ 2 （前走車の位置情報は最大で2つ）
  Large input の場合：1 ≤ N ≤ 2,000 （前走車の位置情報最大2,000）
• Small input の場合：1 ≤ A ≤ 10 （加速度最大10パターン）
  Large input の場合：1 ≤ A ≤ 250 （加速度最大250パターン）
• 1.0 ≤ ai ≤ 9.81 （加速度の最大は 9.81m/s²（重力加速度））
• 0.0 ≤ ti ≤ 10⁵ （前走車の位置情報の時間は最大100,000秒）
• 0.0 ≤ xi ≤ 10⁵ （前走車の位置は最大100,000m）
• ti < ti+1 （前走車の位置情報は必ず時間昇順）
• xi < xi+1 （前走車の位置も昇順でバックして戻ったりしない）
• t0 = 0 （最初の前走車の位置情報は時間0秒）
• xN-1 ≥ D （最後の前走車の位置情報は必ず家より遠く）

解き方はいずれ記事にします。
解いたコードはこちらにあります。