TCO18 MM R1 RoadsAndJunctions

方針

序盤

置く候補を全探索し、置いたときにスコアが大きくなる順に置いて行った。 盤面がでかくて全探索できないときは探索する点を間引いた。

終盤

  1. 焼き鈍しを9400ms実行。遷移は以下の3つで、失敗確率0での解を求めた。

    • ランダムにjunctionを置く
    • 隣へ移動する
    • junctionの削除
  2. 失敗確率も考慮し、期待値が低くなるように1.で求めた点を多重化

反省点

  • yoursの期待値の最小化ではなく、(yours^-2)の期待値を最大化をする発想がなかった
  • 期待値の計算が適当
  • GCEでテストできるようにしていたが、環境構築に失敗していて、最終日までその失敗に気づかなかった(ずっと初期に書いたコードでテストされていた、途中でおかしいなとは思ったんですけどね…)
  • パラメータの調整の時間がもったいなかった(雑で良いので自動調整できるようにしたい)

良かったところ

  • 1週間頑張れた(えらい)
  • EMSTのO(nlogn)解法のような、面白そうだけど効果が薄そうな実装はせず、より効果の高そうな方針の検討に時間を割いた。(初期頂点から構成されるMSTの最長辺の長さで平面を分割するお手軽高速化は行ったけど、よく考えると非常に遅くなるケースあるしやらないほうが良かったな…)

ローカル1000ケースで評価して焼き鈍し解法のほうがよかったのでそっちを投げたけど、standingsでは下がっていた。もしかしてTLEしていたのかな。

別に着るわけじゃないだけどTシャツ獲得を目標にして残りを頑張ろう。

復習

  • 自動調整できるようにする
  • 期待値計算の見直し
  • (yours^-2)の期待値を最大化をしてみる
  • コードの書き直し