Hatena::Grouptopcoder

hama_DU@TopCoderへの道

2012-05-28ARC003

ARC003 C 暗闇帰り道

|  ARC003 C 暗闇帰り道 - hama_DU@TopCoderへの道 を含むブックマーク はてなブックマーク -  ARC003 C 暗闇帰り道 - hama_DU@TopCoderへの道

  • 方針を考える。
    • ダイクストラする?
      • (現在位置,時間)を状態に持つ
      • 500 * 500 * 1000 ぐらいになっておそらく間に合わない。
  • しばらく考える
    • 二分探索で、通れる明るさの上限を決めてしまおう
      • これだと現在位置だけを状態に持てばいいので、 500 * 500 * (二分探索の回数) で済む。
    • これでよさそう。
  • 実装
    • 特に詰まること無くサクサク。
    • 各明るさの初期値 (i:1〜9) について、n時間たった時の明るさを予め dvalue[i][n] に計算しておく
  • 出してみる。
    • TLEしてしまう。あれ?
    • 二分探索で誤差がe-10ぐらいになったら打ち切るようにしてみる
  • 再提出
    • 今度はWA
    • 到達不可の場合は -1 を出力しなければならないが、その判定がミスってる
      • 二分探索する前に、到達可否を調べるコードを書いた。
  • 提出。やっとACがもらえた。この時点で残り30分。