問題
20x20のグリッドグラフ上に、0〜39の数字が書いてある
0から始めて昇順に全ての数字を訪問するという問題
移動は、1マスずつの移動と、壁まで一気に滑走することができる
また、自身の4方にブロックを追加したり、取り除いたりできる
解法
必要な時にブロックを過去に作ったことにする、過去改変貪欲を実装しました
初めて実装したので、最適な書き方では無いと思いますがご了承ください
ビジュアライザ
概要
0番から順に、bfsで次の数字へ到達する最短経路を探索し最初に見つかった経路で行動します
0→1は、過去改変する過去が無いのでただ滑走or移動の行動になります
行動の復元時に、各マスの上下左右のマスに対して過去改変用の情報を書き込んでおきます
すると以降の探索時に、過去の場面でブロックを作ったことにする(取り除いたことにする)ことが可能になります
小さい盤面で説明します
過去改変パート
過去にブロックの変更を行うには、ターン数と方向だけ分かっていれば良いです
移動を伴う行動の出力配列と、ブロックを変更する行動の出力配列を別に持つことで、過去に操作を挿入しても移動のターン数は変更されません
注意としては、移動で乗るマスとブロックに変更を加えたマスは、改変用の情報を消しておく必要があります
コスト2の行動が増えるため、普通のbfsでなくダイクストラ法で最短経路探索を行う必要があります(012bfsでも良いです)
経路探索中に通ったマスをブロックに変えてしまう操作や、滑走で壁として使ったブロックを取り除くような操作をすると、出力が壊れてしまいます
必要なブロックの情報を持ちながら探索するか、ブロックの操作時に行動を復元して判定を行うことで対策できます
提出コード
上記の過去改変貪欲を実装することで、score=218,052で本番49位のスコアを出すことが出来ます(実行時間は7msです)
Nimの提出になります
延長戦
本番中は、ブロックを置く場合のみ過去改変を行い、ブロックを取り除く操作は1マス移動時のみしか行えていませんでした
ブロックを取り除く操作も同じく過去に”やったこと”にできるため実装します
すると、score=218,574で本番28位のスコアを出すことができます
また、実行時間が余りまくっているため乱択山登りも実装してみます
bfsでの探索中に、過去改変をする確率を90%にして実行時間の限り回します
乱択ではなく、本当はビームサーチを実装した方がよいですが、時間に限りのある短期AHCでは乱数を使って、得点の上振れを期待するのも良い作戦だと思います
実行すると、score=219,600でなんと本番10位相当になりました！
最終ビジュアライザ
おわりに
過去改変貪欲は、AHC042でadminのwataさんが使われていて、
Submission #62337792 - AtCoder Heuristic Contest 042 良い実装はそちらを見て下さい
AHC042より今回の方が、過去改変という意味では理解や実装がしやすいので、取り組みやすいかなとは思います
今回もなんとかレートの増価を継続できました
3:30までバグがとれず、score=204,033で終了しそうでしたが、諦めずにバグを探し続けることで何とかなって良かったです
問題を上手く分割して、小まめにテスト出来るような実装手順を確立するのが、短期に向けた次の目標になりそうです
全体50位を目指せそうにもなって来たので引き続き頑張ります
