ビビジランテソンテネグロホメストーニカルマンドーレポポス

さあ、いつまでたってもオレンジコーダーになれない子はどんどんしまっちゃおうねー

HACK TO THE FUTURE 2020予選 参加記

HACK TO THE FUTURE 2020予選に参加しました。
最終成績は4970204点で、なんと予選1位でした！！！
まさか、自分がコンテストで優勝できるとは全く思っていなかったので、
メチャクチャ嬉しいです！！！！
今回は、優勝記念に参加記を書こうと思います。
自分が考えたことをなるべくたくさん書いた結果、読みにくい文章になっていて申し訳ないですが、頑張って読んでいただけると幸いです。

問題概要

まあ、問題概要は説明しなくても大丈夫ですよね？
A - ロボットの誘導

コンテスト中にやったこと

2:30 01BFS解法の実装 (4965088点)

とりあえず、ロボットがたくさんあるとややこしいので、ロボットが1台だけの場合を考えようと思いました。
ロボットを1台確実にゴールさせる方法があれば、その方法を使って貪欲にロボットをゴールさせれば良さそうだなあとか考えていました。
ロボットが1台しかない場合、方向案内をなるべく減らしつつ、ロボットが通るマスの数を増やせば良さそうです。

ひとまず、方向案内を減らすことだけ考えてみます。
これは曲がる回数を減らすということに等しいので、 曲がる場合のコストを1、そうでない場合のコストを0とすれば、01BFSを使って最適な経路を求める事ができます。
後はロボットが通るマスの数を増やせば良くて、これは01BFSの実装をちょっと工夫すれば可能です。（このあたりは実装が面倒なので、自分が書いたコードも若干バグってる気がします...）

最終的なスコアを最大化する、すなわち、曲がる場合のコストを10、一度も通過していないマスを通過するコストを-1、それ以外のコストを0とした場合の合計コストを最小化するというアイデアも考えられますが、僕はこれを捨てました。
というのも、これはコストが負の値を取るような最短経路問題に帰着されるので、計算量が増えて面倒だし、負閉路が出てきても困るなあと思ったからです。

以上の過程を経て、ロボットを1台確実にゴールさせる方法が完成したので、後は各ロボットを順番にゴールさせるだけです。
この方法を使って全てのロボットをゴールさせられるかどうかについては、この時点では考えていませんが、とりあえず貪欲にやってみます。

まず、ロボットを1台ゴールさせて、その経路に応じて方向案内を埋めます。
次に、方向案内を埋めたフィールドで同様にロボットを1台ゴールさせます。
以上を全てのロボットについて行うことで、上手く行けば全員ゴールさせられるだろうという見込みです。

ここで、ロボットをゴールさせる順番について考える必要が出てくるのですが、とりあえず入力で与えられた順番で固定することにします。

以上を踏まえて、実装をした結果がこちらです。
Submission #8250246 - HACK TO THE FUTURE 2020予選

4965088点という非常に高い得点を獲得することができました。この得点は最終成績11位相当のスコアであり、ツカモさんのツイートをみる限りでは一般枠通過ラインの得点です。
この解法はかなりアルゴ色が強いため、マラソンマッチがあまり得意ではない人でも予選突破が可能なことが証明されたかなあと思っています。

しかし、ここまでで約2時間半が経過しており、初動にしては時間がかかりすぎているなあと反省しました。
初手はもっと素直で実装しやすい解法を試すべきなので、今後は気をつけていきましょう。

また、スコアの計算式を見る限り、ロボットをゴールさせることで得られる得点が大きいので、 ロボットを全員ゴールさせることを優先するという考察の方がより自然であり、 そのあたりをあまり考えなかったのも良くないなあという気持ちになりました。
ただ、上記のアイデアを実現するためにはBFSを実装する必要があり、BFSの実装はそこそこ時間がかかるので、 これを経由せずに済んだのはかなりラッキーだったなあと思いました。
まあ、僕の解法もそこまで飛躍した発想ではないので、そこまで悪くはなかったかなあと思います。
今回は、解法ガチャが大成功したので、メチャクチャ運が良かったです。

3:00 使うロボットの順番を乱択 (4966980点)

先程の解法をSubmitした結果、暫定1位になれたので、とても驚きました。
しかも、先程の解法には自明な改善点がたくさんあるので、もうウキウキですｗｗｗ

先程の解法では、ロボットをゴールさせる順番を固定していましたが、とりあえず順番を乱択することにしました。

その結果がこちら。
Submission #8251165 - HACK TO THE FUTURE 2020予選

これで4966980点を獲得し、得点を増やして暫定1位のままという結果になりました。
この時点で、コンテスト開始から3時間が経過しました。

この得点、最終成績4位相当のスコアなんですね、ヤバいなあ...

3:30 使うロボットの順番を山登り法で最適化 (4968361点)

ロボットをゴールさせる順番を乱択したので、次は山登り法で改善していきます。
遷移は適当に2点スワップにしておきます。

結果はこちら。
Submission #8251886 - HACK TO THE FUTURE 2020予選

これで4968361点を獲得し、得点を増やして暫定1位のままという結果になりました。
この時点で、コンテスト開始から3時間半が経過しました。

この得点で、最終成績3位相当のスコアみたいです。
最終成績2位のスコアを上回るスコアが出たのはかなり終盤だったので、1位と2位が相当強かったんだなあと思いました。

4:00 使うロボットの順番を焼きなまし法で最適化 (4968116点)

先程は山登り法を試したので、次は焼きなまし法の出番です。
パラメータを色々変えて一番良かったのがこちら。
Submission #8252337 - HACK TO THE FUTURE 2020予選

一番良くても4968116点なので、最高得点を更新することはできませんでした。
しかし、まだ順位は1位のままでした。

この時点でコンテスト開始から約4時間経過しており、自分が1位になってから約1時間半の間、順位がずっと1位のままだったので、
「普段TLとかで見ていた強い人達は一体どこへ行ってしまったのかな...？」
とか、考えていました。

考察タイム

点数が伸びなくなったので、きちんと考察（を整理）することにしました。

まず、得点やビジュアライザを見る限りでは、ロボットを全員ゴールさせることは難しくないため必須だとわかります。

また、全てのマスのうち約2割がブロックマスであり、なおかつ、それらが一様ランダムに選ばれることから、 「あえて方向案内を増やして遠回りをすることでロボットが通るマスを増やし、その結果スコアが増える」 といったことを実現するのはおそらく難しいだろうと考えました。
さらに、方向案内のスコアの重みが-10なのに対して、通ったマスのスコアの重みは1であるため、 やはり、方向案内は可能な限り減らすのが得策だろうという結論になりました。

そして、スコアの伸びがそんなに大きくないことを考えると、通ったマスの数もできれば増やすほうがいいとわかります。

以上の考察を踏まえると、大まかな方針は今まで通りで良さそうだと結論付けることができました。

6:55 山登り法をチマチマ高速化 (4969195点)

というような考察をしていると、
「あなたの01BFS解法、制限時間内における試行回数はどれくらいですか？」
という天啓を得たので、調べることにしました。

コードテストを使うと、試行回数が80回ほどしかありませんでした。
それはそうで、僕の01BFS解法はO(MN2)でそこそこ重い計算のため、試行回数が稼げていませんでした。
そこで、焼きなまし法ではなく山登り法を使うことにして、01BFSの高速化を行うことにしました。

とりあえず、小手先の高速化として、多次元配列を1次元配列に潰すという改善を行いました。
さらに、実行時間ギリギリまで計算を回すようにコードを書き換えました。

以上を実装した結果がこちら。
Submission #8257165 - HACK TO THE FUTURE 2020予選

コードテストで調べた試行回数は330回程度で、最初の実装から約4倍の高速化に成功しました。
そして、4969195点を獲得し、得点を伸ばして暫定1位を維持しました。
この時点で、残り時間が1時間ほどとなりました。

もう、ここまで来たら絶対に優勝したいなという気持ちでいっぱいでした。

7:18 方向案内をゴールとみなす (4969837点)

ほかに高速化できるところはないかを探すために、落ち着いて考察します。

先程の考察で、あえて方向案内を増やすことに意味がないことがわかりました。
なるべく方向案内を減らすためには、誰かが通ったルートに合流した時点でそのルートに乗っかるのが一番だとわかります。
なぜなら、01BFS解法においては、ゴールにたどり着ける経路しか考えないので、誰かが通ったルートを使えば確実にゴールできますし、 さらに、合流した時点で方向案内をそれ以上設置する必要はないからです。
よく考えると、誰かが通ったルートに合流するタイミングというのは、「方向案内のマスを踏んだタイミング」に等しいことがわかるので、 方向案内のマスをゴールとみなしてやると、01BFSの計算の枝刈りができます。

結局、僕の解法は、序盤で操作したロボットが作った流れに残りのロボットが乗っかっていくという仕組みで動いていたのだと気づきました。
さらに、方向案内は踏んだ時点で勝ちなので、あるロボットのために設置した方向案内が別のロボットの邪魔になることはなく、 それゆえに、貪欲に1台ずつロボットをゴールさせても、全てのロボットをゴールさせることが可能なのだと理解しました。

というわけで、これらのアイデアを実装した結果がこちら。
Submission #8257955 - HACK TO THE FUTURE 2020予選

コードテストで調べた試行回数は800回程度で、最初の実装から約10倍の高速化に成功しました。
そして、4969837点を獲得し、得点を伸ばして1位の座を死守しました。
今回のコンテストでは、01BFS解法とこのアイデアが決め手になったような気がします。

追記 (2019/11/05 01:28)

確かに誰かが通ったルートを通るのは有効ですが、合流する際に（順路と逆向きの方向案内を用いて）ルートを逆走しないという条件を満たす必要があります。
確か、コンテスト中はそのあたりをあまり考えずに適当に修正して上手く動いたので、そのまま提出した記憶があります...
そのあたりをきちんと考えてソースコードを修正すると、試行回数が1000回程度になり、さらに焼きなまし法を用いると得点が4970314点と本番の最高得点を更新することができます。
Submission #8293678 - HACK TO THE FUTURE 2020予選

僕のソースコード（および解法）は全体的にバグってる可能性が高いので、あまり参考にしないことをオススメします。

7:49 焼きなまし法に変更 (4970204点)

もう残り時間が少ないので、出来ることは限られています。
どうしようかと思っていると、
「あなたの山登り解法は、制限時間を増やしたときにスコアが増えますか？」
という天啓を得たので、制限時間を30秒に増やしたときのスコアを眺めます。

スコアの伸びは小さいように見えたので、山登り法から焼きなまし法に変更することにしました。
（もはや、これくらいしか出来ることがなかったというのもありますが...）
そもそも試行回数があまり多くないので、焼きなまし法を使うのは適切でないように見えますが、 01BFS解法が優秀なので何とかなるだろうと信じることにします。

ラストスパート。パラメータを色々変えて、提出しまくります。
焼きなまし法のパラメータは、少し前に色々試したので、おおよその目星はついています。
後は全力で祈るだけです。どうか良いスコアが出ますように...。

というわけで一番良かった結果がこちら。
最終的に4970204点を獲得し、大台の497万点に到達することができました！
そして、競プロ人生で初めて、コンテストで優勝することができました！！！
Submission #8259128 - HACK TO THE FUTURE 2020予選

感想

振り返ると、自分が1位になってから5時間半の間、ずっと1位を独走し続けたんですね...
率直に言って物凄くカッコよくないですか？（僕は自分に起きた出来事だとは思えないくらいカッコいいと思います）
2位のats5515さんとの得点差はごくわずかだったので、最後まで全力で走り続けて良かったなあと思いました。

かなり運要素が強かったですが、なにはともあれ、競プロ人生初の1位なので、これからはこの実績でガンガンイキっていこうと思います。
本戦にはおそらく参加するはずなので、次は競プロ人生初の賞金獲得を狙っていこうと思います（あまり期待はしてないけど）。

（このツイートに解法ツイートがぶら下がってるので、良かったら参考にしてください）

おまけ（没アイデア集）

ゴールから1回だけ01BFSの計算をしてよしなにやる

ゴールから01BFSをするやつを盛大にバグらせたのでボツ。
chokudaiさんが公式放送で言っていたツリーをよしなに構築できれば良いなあと思っていたけど難しそう。

01BFSの計算の途中経過を保存

毎回、全てのロボットについて01BFSを計算するのは無駄だなあと思っていたので、なんとかしたいなあと思っていたけど時間が足りず。

2点スワップでのロボットの選び方を工夫する

おそらくこの解法だと、序盤で操作するロボットを何にするかが重要になってくるはずなので、序盤のロボットが多めに選ばれるように乱数を調整すべきだったかなあとか思いました。

ロボットの順番で良さそうなやつを色々考える

例えば、ゴールから近い（遠い）順からゴールさせるとかは考えるべきっぽかったです。
個人的には、ロボットの距離が近いやつ同士を一つのグループとしてみなすクラスタリングをして、クラスタごとに最適化したらどうかなあとか考えていました。