AHC068参加記
はじめに
AtCoder Heuristic Contest 068 に参加し、555位(perf1088 )でした。
今回までは短期AHCでの生成AIの使用がOKでしたが、次回の短期AHCでは使用禁止になるので先を見据えて生成AIなしでやってみることにしました。
成績も成績なので有益なことはあまり書いていないですが、生成AIなしでやるとどうなるかという意味ではもしかしたら参考になるかもしれません。
問題
- 正方形状のグリッドマスがあり各マスに番号がかかれたカードが置かれている
- グリッドのマスの境界の一部には仕切りがある
- 仕切りで遮られない長方形を選んで上半分と下半分、または左半分と右半分のカードを入れ替える操作を行うことができる
- なるべく少ない操作数でカードを正しいマスに並べ替えるのが今回の目的
解法
操作は隣り合うカードを交換する操作のみとし、カードを1枚ずつ順番に正しいマスに運びました。一度処理し終わったカードの位置は固定し再び移動しないようにしています。
1. 処理するカードを決める
2. カードの現在位置から目的地マスまでの経路をBFSで求める
3. 上記2で求めた経路に沿って縦2x横1 or 縦1x横2の長方形を選ぶ操作を行うことでカードを交換して運ぶ
処理するカードの順番
ランダムに選んだマスを根とする木を乱択DFSで作成し、DFSの帰りがけ順に操作しました。
問題文中の例を見ると、なるべく端・壁際から順番に処理したほうがよいのだろうと思い、最初は次数が少ないもの順としていたのですが、その方法だと途中で連結が切れてしまい全部のカードを処理できない問題が発生しました。
連結が切れないように毎回UnionFindで確認することも試みたのですが、それだと処理時間が間に合わなくなり断念。
グリッドから木を作って木の葉に当たる方から処理すれば連結が切れることなく処理できると考えてこの案に落ち着きました。
DFSで作った木から順番を決めることで連結は切れなくなりましたが、端・壁際でないマスが比較的早い段階で処理されてしまい効率が悪いことには、ビジュアライザを見てすぐ気づいたのですが、コンテスト中に解決することはできませんでした。
なお、根とするマスやDFSの向きはランダムなので、処理時間いっぱいまで山登りをしています。
経路の求め方
シンプルなBFSで経路を求めています。
注意した点としては、処理し終わって正しいカードが置かれるようになったマスは固定するため、処理が終わったマスはその都度グラフから辺を削除するようにしました。
カードの移動
縦2x横1 or 縦1x横2の長方形を選んで操作をすると、隣り合うマス同士のカードを交換する形になります。これをBFSで求めた経路に沿って行い1マスずつカードを正しい位置まで移動していきました。
あらかじめBFSで求めた経路に沿って連続した2マスを指定しているため、長方形には仕切りが含まれないことは保証されており、比較的シンプルに実装できるためこの方法を採用しました。
効率は悪いため可能であればより大きな長方形を指定して複数マス分を一気に進められるようにしたかったのですが、コンテスト中にはできず断念しました。
コンテスト後に試した解法
木の作り方をDFSからBFSに変更
コンテスト後の解説を眺めていて気付いたのですが、先程も書いた通りDFSで木を作ると端・壁際でないマスが比較的早い段階で処理されてしまいます。処理されたマスは固定され、壁扱いになってしまうため、後の経路の効率が悪くなってしまう問題がありました。
DFSのかわりにBFSを使って木を作ることで端・壁際から順番に処理したいという意図に近い形で順番を決めることができます。
これをすることでスコアが少し改善し本番538位相当に改善しました。
カードを1マスずつ移動から複数マス移動に変更
1回の操作で複数マス分カードを移動できるときは、それを可能としました。
（操作に対する制約から直進移動のみを考えます）
例えば3マス分の移動を1回の操作で可能かどうかをチェックするときは
・対象の3マスを含む
・仕切りを含まない
長さ6マスの長方形が存在することを確認しました。
上記のチェックを使って、BFSの経路に沿って尺取り法を使うことで1回の操作で処理可能な区間を特定していきました。
これをすることでスコアが大幅に改善し本番386位相当まで順位が上がりました。
反省点
また、前回の反省で
「乱択DFSを使ってグリッドから迷路を作る（グラフの辺を削って木を作る）」という手法は、感想戦を眺めるまで思いつきませんでした。こういった手法は汎用性がありそうでAHCの基礎として重要だと思いますが、自身の基礎的な力がまだまだ不足していると感じました。
と言っていたのですが、今回この反省から乱択DFSで木を作るという着想が得られたので前回の反省を活かして課題を解決できたというのはよかったと思います。
悪かった点としては、前回の反省を活かせたのはよかったものの、木を作るところでBFSのほうが望ましいところを、反省文そのままにDFSを使ってしまった点です。
グラフから木を作るときにBFSとDFSどちらがよいかというのは過去にも（AHC041など）あった気がしますので、こういった汎用性のある事項は次回以降に活かしたいと思います。
感想
問題文を読んだときに全部のカードを並べきるところがスタートラインかと思いましたが、スタートラインに立つだけで2時間半ほど使いました。自分の実力からすると生成AIなしであればまずはコンテスト内に実装しきれてよかったという感想です。
※この辺りは実装力に左右されるので参考までに記載するとコンテスト開催時点のアルゴのレートは1048です。
自分でしっかり考えを整理しながら進められたためか、充実感のあるコンテストでした。結果が出ないことに対して先に逃げ道を作っておいたという気もしないではないですが、この辺のことを言い出すときりがないので、参加してよかったと思えたのでOKとします。
あとは解説方法をまだ見れていないので、これから見て上位解法を勉強しようと思います。
ここまで読んでくださりありがとうございました。
