HAL研究所プログラミングコンテスト2020 に参加した。課題や競プロなどによって、3 日ほどしかできなかった。
実装
地形の境界に注目した。境界で、かつ格子点上の点と、巻物、最初のウサギの位置の点すべてを頂点とし、そのなかの任意の 2 つの頂点間の距離を、地形に応じた距離(砂地なら 10/3 倍、池なら 10 倍にする)として計算する。これは、通過するマスを 1 つずつ見ていって計算した。
その後、巻物の点、最初のウサギの位置の点からダイクストラを回し、巻物の点と最初のウサギの位置の点を頂点とする完全グラフを作成する。2 点の距離は、ダイクストラによって得られたパスに沿って実際にウサギが飛んで行った時の飛ぶ回数とした。これは、二分探索を改良した形で実装した。
この完全グラフを得た後、巡回セールスマン問題を解いた。(2^N)*(N^2) かかる方法で実装した。
そして、得られたパスに沿って進む、という風に書いた。
高速化
実装にかなりの時間がかかったうえ、実装すると全体で 140 秒かかってしまい、制限時間 6 0 秒を超えてしまった。二分探索の部分を高速化することで 100 秒まで落としたが、この時のボトルネックとなった、巡回セールスマン問題の部分と地形に応じた距離を調べる部分を高速化することができなかった。
やりたかったこと
二分探索みたいにすることで、よくなる時と悪くなる時があった。悪くなる時は、平地から少し先の池の部分に飛んでしまうようなパターンであった。この時に平地のぎりぎりで止まる、みたいなことをしたかった。
また、巻物を境界付近に持ってくる(巻物がある地点を踏んだらすぐ次に行く)実装もしたかった。
反省点
実装力が足りない。
また、定数倍高速化を今まであまりしてこなかったので、それほどできなかった。
