もふふろぐ

ハル研究所 プログラミングコンテスト2015

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

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

配達順の探索では、BitDPだと分かりながらも配達を上手くDPに落とし込めず手間取ってしまいました。何とか最低限の実装を書いたものの、時間帯無指定の荷物の振り分け方が全く分からず、最適解を出せるコードを提出できませんでした。最後の手段として探索を強制的に打ち切り、判定を無理やり通した結果が上記のスコアになります。

今年のプロコンは最適解を出せることが前提の雰囲気だったので、最適解を出すぞと意気込んでいましたが、プロコンの経験不足があらわになる結果に終わってしまいました。来年までにプログラミングをできるようになりたいところ。