もふふろぐ

ハル研究所 プログラミングコンテスト2015の最終結果が今日発表されました。 私は最終スコア34,118,110、総合50位（学生41位）でした。 以下雑多な感想です。

結果発表の解説同様、まずは荷物間を最短で移動できるように迷路の経路探索をしました。 2次元の地図上の問題をグラフの問題に単純化します。 時間短縮を意識して、あらかじめ不要な通路を消す処理も書きました。

配達順の探索では、BitDPだとは分かりながらも上手く落とし込めず手間取ってしまいました。 何とか最低限の実装を書いたものの、時間帯無指定の荷物の振り分け方がわかりませんでした。 最後の手段としてヒューリスティック問題のように探索を打ち切り、正誤判定を通した結果が先述のスコアになります。