AHC018参加記

519位

問題のリンク

考えたこと

初期解

問題に取り組みはじめたのが2/25の夜とコンテスト終了まで24時間を切っていたのでとりあえず乱択をしてみた。 時間の限り家の順番をランダムに並べ、各家ごとに1番近い水源かすでに岩盤が破壊されているセルへの最短経路を求めてみた。

順列

寝て起きて10時を回っていたので新たな解法を思いつくのは無理だと思い、初期解から少ない変更でスコアが改善しないか試してみることにした。 初期解では家の順番をランダムに並べていたが、1番近い水源の個数順に並べ時間の限り順列を試してみることで少しスコアが改善した。

Kによる探索方法の場合分け

上の順列で何ループできているのかコードテストで試してみると、約1000ループほどできていた。 つまり、$K \leq 6$の場合、全パターンの探索が可能である。 $K \leq 6$の場合は家の順番を全探索を行い、それ以外は初期解を踏襲し乱択をすることでスコアが改善。

Cによるパワーの場合分け

探索方法について新たなアイデアが思い浮かばなかったので、パラメータをいじることを検討した。 今まで入力として受け取っている$C$について考慮していなかったので、$C \leq 16$とそれ以外とでパワーを変えることでスコアがさらに改善した。

最終提出

パワーの場合分けについて何パターンか試して1番スコアが良かった以下のパターンでシステムテストに挑んだ。

if (C <= 2) P = 20;
else if (C <= 4) P = 40;
else if (C <= 32) P = 80;
else if (C <= 64) P = 162;
else P = 334;

なんでや！チルタリス関係ないやろ！

感想

初めてヒューリスティックに挑んだAHC011ぶりに水パフォが取れて良かった。

Twitterで流れてきた試し掘りなどを行なって岩盤の頑丈さを求める解法を見てなるほどと思った。 長期コンは色々と試せそうなことがあると勉強になった。

今回の参加記を書くにあたり図を作成するために出力を初めて行なったが、そこで自分の解法が思い通りではなかったことに初めて気づいた。 セルが壊れなかった場合パワーを2倍にするという処理を書いていたつもりが、ループのたびにパワーが初期化されていて2倍になっていかなかった。 やってしまったと思い、急いで思い通りの解法を提出したがスコアが悪化した。 ヒューリスティックあるある。