AHC063参加記
はじめに
AtCoder Heuristic Contest 063 に参加しました。
その参加記です。
問題
問題はこちらです。
自分なりにかいつまんで言うと
- 正方形状のグリッド上を蛇が移動できます。蛇の体自体もグリッドの連結した数マスを占めます。
- グリッドのマス目には色のついた餌が散らばっています。
- 蛇が餌を食べると蛇のしっぽが長くなり、長くなった部分は食べた餌の色になります。
- グリッド内の餌をすべて食べたときに蛇の色が指定通りになっている、つまり正しい順番で決められた色の餌をできるだけ少ないターン数で食べていくのが目標です。
- ただし、胴体と頭が重なると胴体を噛みちぎります。噛みちぎられたしっぽ側はその位置で再び餌となってグリッド上に配置されます。
つまり、順番通りに餌を食べられなかった場合は、噛みちぎることで途中からやり直しすることができます。
解法
ルールベースに一部ビームサーチを採用しました。
正しい餌を食べるルートをビームサーチで一気に決定し、正しい餌が見つからない状況や間違った餌を食べてしまっている状況はルールベースで打開。
具体的には、完成するまで以下1～3のいずれかの行動をとります。数字が小さいほうが優先です。これを完了するまで（もしくはターン数や制限時間に達するまで）繰り返します。
1. 間違った餌を食べてしまっている場合
頭から間違った餌までのどこかの胴体を噛みちぎって分離し、その後正しい位置まで胴体を復元。
胴体を噛みちぎるための経路をBFSで求めています。ただし最短経路だけにすると手詰まりになりやすいため噛みちぎることが可能な行き先マスをすべて求めてその中からランダムに決定するようにしています。
2. 正しい餌が見つかる場合
途中で違う餌を食べることなく、かつ胴体を噛みちぎることなく正しい餌を取ることができる場合、次の餌までの移動を1遷移としたビームサーチを行い、最も多くの餌を取り続けられるルートを採用。餌の数が同じルートが複数ある場合はターン数が少ないものを採用としました。
次の餌までの移動を1遷移とした理由は、自分がビームサーチをほぼ初採用という状況だったのでビームサーチで解くところを単純化したかったためです。例えば1ターン1遷移などとしたときに評価関数をどうしたらよいのか思い浮かばなかったので、今回は「間違った餌を胴体に含んでなく、正しい餌だけを順番に食べていける状況」だけを抜き出してビームサーチにすることで評価関数などを単純にするという方針で行きました（それ以外の状況はルールベースの1.や3.に任せています）。
3. 正しく餌を取ることが困難な場合
間違った餌を取ったり胴体にぶつかってもよいのでとにかく次の正しい餌まで向かうルートをとるようにしました。
ただしその場合も間違った餌や胴体になるところはなるべく通らないようなルートを採用するようにしました。
（胴体の位置や間違った餌への移動のコストを高くしておいてダイクストラ法で経路を決定）
ここで移動途中で胴体の噛みちぎりが発生した場合は求めた経路の移動はそこでストップし、胴体の復元を行うようにしています（復元した後は再度上記優先順位の判定からやり直し）。
工夫した点
自分なりに工夫した点です。上級者向きのことは書いてなく（むしろ上級を目指すなら逆に微妙な点が多いかもしれません）、ビジュアライザを見ていて気になった点を改善したいけどどのように実装しようかという悩みへの対処みたいな視点が多いです。
蛇の状態の持ち方
dequeを2つ持って管理しました。
shape: 蛇の位置
color: 蛇の色
1ターン分の移動に対しては以下の通り操作します。
・移動先が胴体の場合（噛みちぎりが発生するケース）
shape: 末尾から順番に削除していき移動先の座標が見つかったところで止める
color: shapeと同じ数になるまで末尾から順番に削除
・移動先に餌がある場合
shape: 先頭に移動先の座標を追加
color: 末尾に移動先の餌の色を追加
・移動先に何もない場合
shape: 末尾を1つ削除、先頭に移動先の座標を追加
color: 何もしない
ここで胴体を噛みちぎるケースで末尾から取り出した要素をさらに別のdequeに入れておくと復元に使うことができます。
※説明を省略していますが餌の分布は別途配列に持ち、あわせて管理しています
胴体噛みちぎり発生の判定
グリッドのマスに対して最後にそのマスに頭が移動したのは何ターン目かを配列に持つようにしました。
上記のdequeを見ていくことでも判定はできますが、こちらのほうがより高速に判定することができます。
さらにもう一つメリットがありBFSをするときにdistance配列と組み合わせることでそのマスに到達した時に胴体が残っているか正確に判定することができます。
胴体の復元を途中で止める
胴体の噛みちぎりが発生した時に、噛みちぎった地点から元のしっぽの方へたどっていくと胴体を復元することができますが、ビジュアライザで復元している様子を見ていると完全に復元するより少し手前から実はもっとよい枝分かれルートが存在しているのに復元を優先してしまい、その先で手詰まりがちになるケースがありました。
そこで完全に復元するのではなくあえて少し手前で止めておいて、そこからビームサーチをすることでよい枝分かれルートへ流れていくようにしたところスコアが改善しました。一切復元せず全部ビームサーチ任せでも理屈的にはよさそうですが、ビームサーチが重くなるためかある程度は復元したほうが良い結果になりました。今回は最大限復元可能な地点の8手前で止める方針としました。
BFSをするときの上下左右の順番をランダムにする
最初はBFSで探索するときの上下左右の順番を固定にしていました。ただ、ビジュアライザを見ていると、上下左右の順番を変えるだけで到達できるのに、固定してしまっているためにルートがブロックされてしまい到達できなくなっているケースがありました。そこで上下左右の探索順番をランダムにするようにしたところ、これだけで結構目に見えてスコア・順位が上がりました。
軽いテストケースは時間が余るので乱数のシードを変えてたくさん試す
ビーム幅は時間で調整するようにしたのですが、それでもNやMが小さいケースでは時間が余ったため、乱数のシードを変えてたくさん試行し、一番スコアがよいものを採用するようにしました。
先ほどの上下左右もそうですが今回はいろいろランダムな箇所を増やすとスコアが改善するケースが多かった気がします（正直自分ではよくわかってないところに入れた乱数が活躍して外すに外せなくなった箇所もあったりしました・・・）
失敗した時の滑り止め解を用意しておく
1. サンプルプログラム解
2. ルールベース解（上記のビームサーチを削ったもの）
3. ビームサーチ解
を用意しておきました（番号順に作っています）。ルールベース解がなぜかどのケースでも安定して完走してくれるのでこれを滑り止め解として用意しておきました。
さらに万一に備えて最悪の場合はサンプルプログラムと同じ解を出すようにしました。システムテストの結果を見る限りサンプルプログラムの解が出力されることはなかったようですが。
結果
最終順位は153位(perf 1900)でした。
全てのテストケースで正しい色が揃えられていて、さらに一番悪かったケースでも相対スコアが770Mなので全体的に安定してたようです。
最終提出
※コードが汚い上に、そもそもKotlinなので参考にならないと思いますが・・・
おわりに
今回も難しかったです。また久々にどっぷり取り組んだ回でした。
AHCに参加するのは16回目となりますが、初めてビームサーチを採用しました（過去に一度取り組んだことはありますがその時はうまくいかず没案になりました）。
初めてということでビームサーチする箇所を単純化して絞った分、ビームサーチをやったにしては控えめなパフォーマンスになってしまった面もありますが、現実的な落としどころを考えて、自分の中では比較的良い結果を得たという意味ではよかったと思っています。
参加記書くのが初めてのため読みづらいところもあったかと思いますが、ここまで読んでくださりありがとうございました。
