AHC011参加記
AHC011に参加した感想です。
はじめに
まず問題文を読むと、空きマスを上手く動かして木を作る問題のようです。 もちろん木とは言ってもグラフの木です。 そんなことできるのか？というのが始めに思ったことでした。
ビジュアライザを見る
文章で読んでもよく分からないので、次にWeb版ビジュアライザを見に行くことにしました。
seed=0の初期状態でもscoreが71429となっていました。どうやらどこかが木になっていればOKのようです。
このパズル、どこかで見覚えあるような？
空きマスを動かして絵を完成させるパズルをどこかで見たはずなのですが、名前が分からないので検索できないことに気付きました。ただ、OpenSiv3Dのサンプルプログラムの中に載っていたことを思い出したので、それを確認しました。どうやら「15パズル」と呼ばれるもののようです。15パズルで検索すると、解法が色々出てきました。完成図さえ分かれば、木を完成させることは可能ということでした。 ただし、木を作ることができなかったので、15パズルの解法を使うことはありませんでした。
ランダムに動かす
木を作る方法が分からないので、とりあえずランダムに動かしてみて得点が上がるならその操作を採用するという方針で実装してみることにしました。
まずは何も操作しない場合を試してみます。
Submission #32106280 - AtCoder Heuristic Contest 011
得点は2869199でした。
次に、試しに操作して点数が上がるならばその操作を採用し、どの操作でも点数が同じならばランダムに操作するように実装しました。ここまで来ると、最初に空きマスがどこにあるか探す関数を作ったり、評価関数を作ったりとヒューリスティックっぽく？なってきました。 評価関数については木のサイズが大きいほどスコアが上がるという条件だったので、UnionFindでそれぞれ木のサイズを求めて、最大値を返すようにしました。すると、得点は5695968になりました。 最初は実行時間制限に間に合うか分からなかったので操作回数を上限の1/3に抑えていたのですが、どうやら余裕で間に合うようです。上限まで操作するようにしたところ、得点は6502898になりました。
ビジュアライザで確認する
これはかえでさんのブログを読んで、この方法は良さそうだな～と前から思っていた方法です。
実録！MC Digital プログラミングコンテスト2022（AtCoder Heuristic Contest 008）参加記 - 競プロ始めました
ビジュアライザを活用し、seedの値を色々変えてバグを探すというものです。本来ならseedを0から100まで全部試すほうが良いのですが、面倒なので切りの良い数字だけ試しました。 明らかに得点が低かった例は、seed=10の場合です。
このように閉路を持つグラフがある場合、その部分が塊のようになって、スコアが下がってしまうようでした。 そこで、閉路を解消するように評価関数を変えました。幸い、UnionFindを使っていたので閉路検出は簡単に実装できました。
閉路検出を使った実装を提出すると、得点は6656767になりました。期待したほど伸びていません。ただ、もう一度ビジュアライザを確認すると、確かに閉路はなくなっていることが確認できました。（なぜ得点が伸びなかったのかは不明ですが……）
回数を増やす
ここで、実行時間に注目するとわずか30~40ms程度で終了していることが分かりました。そこで、「与えられた初期の盤面から空きマスを移動させて得点を伸ばす」という処理を複数回(20回程度)独立して行い、その中で一番高得点だったものを解答として出力することにしました。その結果、得点は8852284になりました。この方法は上手くいったようです。
移動を効率化する
ここまでランダムに空きマスを動かしてきたのですが、よく考えると上に移動した直後に下に動かしたり、左に動かした直後に右に動かしたりするのは無駄ということに気付きました。 そこで、直前の移動を打ち消してしまうような移動となった場合は移動させず、操作回数としてもカウントしないという実装にしました。 また、評価関数の実装を変えて閉路が存在する場合は得点を減点するようにしました。これにより、より積極的に閉路を解消するようになりました。
提出したところ、最初はバグで操作回数を超えてWAになったり、実行時間制限に間に合わせる目的で試行回数を20回から 10回に減らしたために得点が下がったりしました。しかしそれらを修正した結果、得点は約9000000点（システムテストによって得点が書き換えられたので正確な点数は不明）となりました。
まとめ＆反省点
システムテストの結果、得点は547024686点、順位は486位となりました。 反省点としては、問題文をよく読むことが挙げられます。実行時間制限を2秒だと思い込んでいたり（本当は3秒なのに、終わってから他の人の解説を見るまで気付かなかった）、パネルの規則性を読み落としていたり（自力で思いついて勝手に感動していたけど問題文にちゃんと書いてあった）、木ではなくただの連結グラフを作っていたり……
次回は、もう少し順位を上げたいですね。
