HACK TO THE FUTURE2018予選 参加記録

コンテストページ：

HACK TO THE FUTURE 2018予選 - HACK TO THE FUTURE 2018予選 | AtCoder

1位でした。

やったこと

最初の1時間くらい

大まかな解法について考えた。「貪欲後に山登り」が直感だった。オーダーが落ちるレベルの高速化についても考えたが実装できそうな範囲では何も思いつかなかった。この時点ではコードは書かなかった。

1時間後～4時間後

貪欲を実装。あまりスコアが出なかった。高さ100の山が多くなっていたので、最初に多くとりすぎるのがまずいとおもい、同じ高さの山は10個までしか取れないようにした（99212…点、最終135位のスコア（コンテスト終了後に検証））。山登りを実装。遷移はx±1,y±1,h±1の6つ。無限にバグらせ、実装が終わった時には5時間がたっていた（99975…点、最終20位）。

4時間後～5時間後

 ごはん

5時間後～7時間後

山登りの収束チェックをする。余裕で収束しているようなので焼きなましを考える。

焼きなましを実装（99988…点、最終2位）。意外に得点が伸びる。回数をそんなに稼げないと思っていたので意外だった。

細かな改善をしてスコアを伸ばす（99989…点、最終1位）。高速化については何も思いつけなかった。

7時間後～終了

 パラメータを変えたのをローカルのバッチテストに投げたり、順位表のページでF5を押すマシンと化す。

考察、 感想

一般に順序が関係ないならば山登り、焼きなましをしたほうが良いが、問題サイズが大きくて試行回数を稼げないときは、順序を固定するなどして貪欲ベースの探索を行ったほうが良いことがある。この問題の場合、山を配置したり移動させるごとにどうしてもO(N^2)かかって試行回数を多くは取れない可能性があると思い、貪欲と微調整としての山登りを最初に実装した。やってみると山登りが楽に収束することが分かったので焼きなましをした。山登り、焼きなましの近傍は、第一に高速であること、第二にスコア差が小さいことが重要である。焼きなましの場合、局所的なスコアの上り幅の期待値が大きいことや遷移する確率が低そうなところを温度によって近傍から外すことなども重要である。今回の場合、大きく位置を変えても隣へ変えても速度的には大きく変わらないことと、小さく動かしたほうがスコア差が小さそうであることから、x±1,y±1,h±1を近傍にするのが良いと思う.。最終的には貪欲部分には0.5秒も費やさないようになった。ただし、ないよりはあったほうがスコアが良い。

結果的にアルゴリズムレベルでの高速化が大して必要ない問題だったのが運がよかった。アルゴリズムレベルでの改善が本質になるような問題もある。

最終1位とはいえ実装が遅かったり最終盤においてアイディアをあまり出せなかったり反省点は多い。本線も1位目指して頑張りたい。