AHC068参加記
はじめに AtCoder Heuristic Contest 068 に参加し、555位(perf1088 )でした。 今回までは短期AHCでの生成AIの使用がOKでしたが、次回の短期AHCでは使用禁止になるので先を見据えて生成AIなしでやってみることにしました。 成績も成績なので有益なことはあまり書いていないですが、生成AIなしでやるとどうなるかという意味ではもしかしたら参考になるかもしれません。 問題 https://atcoder.jp/contests/ahc068/tasks/ahc068_a 正方形状のグリッドマスがあり各マスに番号がかかれたカードが置かれている グリッドのマスの境界の一部には仕切りがある 仕切りで遮られない長方形を選んで上半分と下半分、または左半分と右半分のカードを入れ替える操作を行うことができる なるべく少ない操作数でカードを正しいマスに並べ替えるのが今回の目的 解法 操作は隣り合うカードを交換する操作のみとし、カードを1枚ずつ順番に正しいマスに運びました。一度処理し終わったカードの位置は固定し再び移動しないようにしています。 1. 処理するカードを決める 2. カードの現在位置から目的地マスまでの経路をBFSで求める 3. 上記2で求めた経路に沿って縦2x横1 or 縦1x横2の長方形を選ぶ操作を行うことでカードを交換して運ぶ 処理するカードの順番 ランダムに選んだマスを根とする木を乱択DFSで作成し、DFSの帰りがけ順に操作しました。 問題文中の例を見ると、なるべく端・壁際から順番に処理したほうがよいのだろうと思い、最初は次数が少ないもの順としていたのですが、その方法だと途中で連結が切れてしまい全部のカードを処理できない問題が発生しました。 連結が切れないように毎回UnionFindで確認することも試みたのですが、それだと処理時間が間に合わなくなり断念。 グリッドから木を作って木の葉に当たる方から処理すれば連結が切れることなく処理できると考えてこの案に落ち着きました。 DFSで作った木から順番を決めることで連結は切れなくなりましたが、端・壁際でないマスが比較的早い段階で処理されてしまい効率が悪いことには、ビジュアライザを見てすぐ気づいたのですが、コンテスト中に解決することはできませんでした。 なお、根とするマスやDFSの向きはラン...