先日参加したAHC002の復習をしたのでそれをまとめます。
AHC002は834,174点で684位でした。
スコア、順位も気になりますが、自分が実装したかったことが出来なかった部分があったので、その部分を修正しようと思い、復習を始めました。
最終的には、TLでよく見た解法のDFSの実装まで実施しました。
復習1
まずは、前回のエントリーの「考えたこと3」で実装しようと試みた部分です。
四隅を目指してルートを設計する実装ですが、四隅をそれぞれ定義しないで、角と一緒くたにしたのがバグらせた原因でした。
この原因を取り除いて、実装した結果すると、このような感じになりました。
意図したとおりに動いてくれましたが、そこまで得点は伸びなかったです。
時計回りと反時計回りを実装して、得点が高いほうを提出解としました。
得点は、460613 / 25000000 でした。
意図したとおりに動いてくれたものの、完全ランダムに進んだ解のほうが2倍弱得点が高かったです。
この方針はこれ以上の改善を考えつかなかったので、ランダムで進む解の得点を上げる要素を考えることとします。
復習2
ランダムに進んだ解を見ると、最後の数手の選択が違っていればもっと先を伸ばせるものが多いことに気づきます。
前回のエントリーにも載せたランダム解も、最後の数手を上ではなく、左か右に進めばもう少し結果はよくなります。
ランダム解の中で、一番得点が良かったものを最後5手巻き戻して、そこを出発地点として再度ランダムに進んでいき、その中で一番得点が良かったものとつなぎ合わせて提出解とするようにしました。
また、この時から、プログラムがスタートした時間と途中経過の時間を記録して、制限時間ぎりぎりになったらfor文を break するようにしました。
TLEもせずに、実行回数を可能な限り増やすために重要な要素だということがわかりました。
このランダム解2つをつなぎ合わせる方針でスコアはさらに伸びました。
得点は、1123998 / 25000000 でした。
復習3
ここまで実装すると、次に考えるのは、復習1と復習2を組み合わせてみることです。
実際に組み合わせて実施してみましたが、得点はあまり伸びませんでした。伸びないどころか少し下がってしまいました。
途中までは四隅を目指して動いていることも確認でき、嬉しく思う反面、最終的には得点が伸びなかったので残念です。
得点は、1001505 / 25000000 でした。ランダムな解を2つつなぎ合わせたほうが得点が良かったですね。
復習4
ここまでは、自分がコンテスト中に考えたことの復習と改善の実装ですが、TLに流れてくる解法で多かったDFSでの実装も試みることにします。
今までのコードをほとんど廃棄して、一からコードを書いていきます。
PAST本でDFS,BFSを学習し、必要な知識はあるはずなのでDFSに必要なデータを揃え、経路を復元できるように考えて実装したら比較的あっさりと実装出来ました。
おおお！！大幅に伸びました！
得点は、2452592 / 25000000 点とこれまた大幅に更新されています。
実行時間を見ると、120msと非常に少ない時間で終了していることもわかりました。
今回の実装は、DFSでスタックに積む順番をU,D,R,Lの順に積んでいたので、このスタックに積む順番をランダムで決定し、最高点を更新したら提出用の解を更新する。ということを時間いっぱい回して提出するようにするとこのような感じになりました。
得点は、3249801 / 25000000 とこれまた大幅に更新することが出来ました。
思ったよりもバグらせることなくDFS解を実装出来たことはうれしかったですが、コンテスト中に書けるようになりたいものです。
コメント