🌲
AHC054_参加記

yunix
2025/10/07に公開
競技プログラミング
ahc
tech
 1. はじめにこんにちは、競技プログラミングのコンテストに参加している yunixです。

AHC054(ALGO ARTISプログラミングコンテスト2025夏)お疲れ様でした!
ALGO ARTIS 初の長期コンテストはいかがだったでしょうか?

個人的には
ビジュアライザを見ながら改善を繰り返す過程が面白い
思い通りに木を配置することをプログラムで書くことが意外と難しく、工夫が必要
などの点で、コンテストをとても楽しむことができました。
運良く最終結果も 7 位と上位に入ることができたので、今回のコンテストでの考察の過程・解法の方針・やりたかったけどできなかったことについて記事にまとめたいと思います。[1]
なお、解法のおおまかな方針については、先日の解説放送でも簡単にお話をさせてもらいました。まだ見ていない方はぜひご覧ください!

 2. 問題概要N\timesN のグリッド状のマップがある
マップにはランダムに木と空きマスが配置されている
また、マップには伝説の花(AA)が 1 つだけ配置されている
冒険者はマップを探索して、AA を探し出そうとしている。冒険者は以下のルールに従って動く:
1 ターンに上下左右の方向に 1 マス移動できる
冒険者は四方の方向を壁または木に到達するまでのマスを観測できる(観測済みマス)
冒険者は目的地を状態として持っており、目的地は以下のルールで決まる:
観測済みマスに AA が含まれる場合: 強制的に AA が目的地になる
観測済みマスに AA が含まれない場合: 観測済みでないマスの中からランダムに目的地を決める

冒険者は目的地への最短経路の方向に 1 マス移動する。なお、この際に未観測マスは全て空白と仮定して経路を決定する
目的地を観測した場合・目的地への到達が不可能とわかった場合・AA を観測した場合には目的地を変更する
最終的に AA に辿り着けたらゲームが終了

毎ターン冒険者の場所が入力から与えられ、冒険者が観測したマスも同時に与えられる(インタラクティブな設定)
ターンごとに冒険者が行動する前に、マップの未観測の空きマスに木を新たに好きなだけ追加できる
できるだけ冒険者が AA に到達するのが遅れるように木を配置してください(かかったターン数がスコアになる)


初期配置のマップ。中央上部分の冒険者がマップを探索して、赤い伝説の花(AA)を探索する。

 3. 考察の過程最終的な方針へ辿り着くまでやったことを(概ね)時系列順で書きたいと思います。

 3.1 自明な解を出力してみる

まずはルールの把握も兼ねて、木を一切追加せずビジュアライザの結果を見てみました(上図は seed=0)。まあそれはそうかという感じですが、木をおかないとすぐ AA へたどり着いてしまい、スコアも酷いものでした。
ビジュアライザを見ながら、
リアクティブに冒険者の動きに合わせて木を置いていくのがいいのか? 冒険者が移動したパスの左右に木を置いていくようなイメージはどうか?
ある程度木をたくさん配置したほうがいい? あまり詰めすぎると冒険者の移動の幅が制限されてしまうので、密度を適度へ保つ必要はありそう。
花の周りに防御機構をつけてみるといい感じになるか?
などと試してみる方針を考えていました。

リアクティブにやるのは少しめんどくさそうだったので、まずは花の周りの防御機構と木をたくさん配置することをやってみることにしました。

 3.2 花の周りに防御機構をつける

花の周りをガードするように木を配置してみました。

これをおくだけで花が見つけられにくくなり、格段にスコアが上がりました(18 点 → 180 点)。

全体でも相対スコアが 5 倍くらい良くなっており、かなり効果がありそうです。
特に、このケースの場合では花のセルが目的地に選ばれている時に花が見つかっており、
ガードがない場合では花以外のセルが目的地に選ばれている時に花が見つかってしまってスコアが低かった
適切に防御を施すことで、花が目的地に選択されるまで引き延ばすことができる
ということがわかりました。
花の周りにこの手の防御機構をつけることは非常に効果がありそうです。

それ以外の場所をどうするのか、ということを考えていくつかレイアウトを試してみました。

これ以降の方針のヒントになったのが次の節のような置き方でした。

 3.3 花の周りに置いたものと同様の木の構造をマップの他の部分に詰めてみる
上の図のように、マップ全体に花の防衛機構と同様のパターンの木を埋めてみました。

seed=0 のケースでは配置的に花がすぐに見つけられてしまうのですが、seed=1 のケースではこの配置が有効に働いており、かなり手数が稼げていました。

seed=1 のケースでどのような事情が起きているのか詳しくビジュアライザを見てみると、以下のようなことが起きていました。
図は 624 ターン目に目的地を見つけて、その次の目的地に移動をし始めたところの様子です。

次の目的地へ移動するためには
木の配置により大きく迂回する必要がある
このルートはすでに観測済みのマスがほとんどを占めており、冒険者に新しい情報をあまり与えない
ことがわかります。seed=1 では類似の事象が何回も繰り返されてスコアが高くなっていました。
このことから、冒険者をマップ上で行ったり来たりさせるような迷路を設置すると効率が良さそうです。

そのためには、
目的地間の移動距離をできるだけ長くする
花が目的地になるまでにできるだけ多く行ったり来たりをさせる(＝できるだけ未観測のマスを残す)
ような配置が良さそうだとわかります。

 3.4 マニュアルモード付きビジュアライザを作成する前の節の考察をもとに、冒険者を右往左往させるような迷路を作ることを考えました。

いくつか迷路のパターンのアイデアはありましたが、公式のビジュアライザを使って試すのは骨が折れそうでした。

そこで、マニュアルモード付きのビジュアライザを自前で開発してみました。


Claude Codeに作ってもらったマニュアルモード付きビジュアライザ
このビジュアライザでは、
入力欄に問題の入力をコピペする
矢印キーでターンを進める
木を置きたい時にはマップをクリックする
ことで、好きなように木を配置してシミュレーションを試せるようになり、試行錯誤の効率が上がりました。

 3.5 左右に分断する方法を思いつく自前ビジュアライザで遊んでいると、マップを左右に分断するような木の配置が良さそうだと気づきました。
このようにマップの外周を回るようなルートを残して、マップを左右に分断するように木を配置します。この時、左右の空間からもう一方に行く際には、必ずマップ外周の長いパスを通る必要があり、手数を稼ぐことができます。

また、この外周のルートは何度も行ったり来たりして通るので、冒険者に新しい情報を与えることも少なくなり、未観測のマスを多く残すことができます。
全体的にこの目論見は良さそうで、順位表のスコアと比べてもかなり良さそうな性能が出ていました。

この配置を実現するための実装に取り掛かろうかと思ったのですが、ここである問題に気づきます。

 3.6 左右に分断する方法の問題点に気づいて、改良を思いつくその問題とは、左右の部屋の移動の際に、冒険者がマップの外周を通って移動する前に、部屋の中のマスをたくさん探索してしまうことです。
上の図のように、冒険者が最初に右の部屋に入ったとします。その次に左の部屋に移動するには必ず外周を通って移動しなければいけませんが、そのことを冒険者は知りません。

そのため、冒険者は中央付近の抜け道を探すために、中央付近のマスを探索し尽くしてしまいます。

このことで未探索のマスは減ってしまい、多くのケースでスコアが伸び悩むことに気がつきました。
冒険者を右往左往させる・そのパスを長く取るという方針は悪くなさそうです。どのようにすれば解消できるかビジュアライザを見ながら考えていました。
最終的に、このように最初に中央を縦断するようなルートを通るようにして、左右に分断をすることを思いつきました。

このようなパスを作ることで、冒険者は左右の部屋の間を移動する際に必ず外周を通る必要があることをあらかじめ把握でき、無駄な探索を減らすことができます。

冒険者に意図的に情報を渡すことで、冒険者の動きを制御することも重要そうな性質の 1 つのようです。

 3.7 分断した領域内での階段状の構造の重要性に気づくさて、左右の部屋を行ったり来たりさせる方針は良いとして、部屋の中の木のレイアウトはどうすればいいでしょうか?

目的地は未観測のセルからランダムに選ばれるので、花が目的地に選ばれることを避けるためには、できるだけ多くの未観測のセルを残すことが重要です。部屋の中を冒険者が行ったり来たりしても、観測されないセルを多く作るにはどのようにするのがいいでしょうか?
これもビジュアライザを眺めていると、階段状の構造を作ることが重要そうだと気づきました。

この図のように、セルが階段状になっている構造では、冒険者が周囲を行ったり来たりしても奥の方に未観測のセルが残りやすくなります。多くの場合、奥の方のセルが目的地に選ばれない限り観測されることはありません。

また、木を増やせば階段状の構造をより深くできて、未観測のセルをより多く残すことができます。
このような構造を左右の分断された部屋の中にできるだけ多く作れば冒険者が右往左往してくれそうです。

 3.8 考察で得られた知見まとめここまでで最終提出につながる考察が得られました
冒険者を行ったり来たりさせるような迷路を作ることが重要
これを実現するためには、マップを 2 つの領域に分けてその間を長いパスで繋ぐことは有効そう
花のマスが目的地になるまで、花を見つけられないようにすることが重要
冒険者へ木の配置を意図的に情報として見せることで、無駄に探索されることを防ぐことができる
分断した領域内では階段状の構造を作ると未探索のマスが多くなって、冒険者の行動が長引きそう
あとはこれらについて細かく詰めて行って最終提出になりました。
これらの考察は大体最初の土日で得られたもので、その後の本質的な改善は乏しかったです。

やりたいけど上手くまとめられなかったことについて後の節で書きたいと思います。

 4. 解法の方針前章の考察を受けて、最終的には以下のスライドの方針で実装しました。


基本的な方針は以下の通りです:
全体のマップを左右に分断して、冒険者が右往左往するようにする

分断された左右の部屋の中に、階段状の構造をできるだけたくさん作る
前章の図にあるような階段状の構造を左右の領域の中にたくさん詰める。この図における「サイズ 5」の大きさまでのパターンを用意して、領域の中に配置する
サイズが大きいパターンから配置できるかを試していく(サイズ 5→サイズ 4→...)。配置できたらその部分を埋めて、次のパターンを試す
追加の木の数が少ない方から優先して配置する。このことによりスペースの有効活用を図る。


花の周りには防御機構をつける
花の周りへ木を配置して、花が目的地に選ばれた時以外は見つかりにくいようにする
単純なガードだと冒険者が花の反対側へ行こうとする際に、花のセルを観測してしまうことがあるので改良した
花の 2 方向を開口部として残しておき、冒険者が花の近くを通りそうになったら開口部を塞ぐようにした


様々なランダム要素を入れて、時間いっぱい試行をしてベストなものを提出する
以下のようなランダム要素を入れた:
左右の部屋の分断のやり方(中央の分断の位置・外周のパスの長さ)
階段状の構造の配置の順番
花の防御機構の開口方向

盤面の評価はシミュレーションを 20 回行ったスコアの平均値を採用した
シミュレーションは計算が重いので、軽くする工夫を行なった
毎ターン BFS をしていると非常に重くなる
BFS をする必要があるのは、新たなマスが観測されてかつ既存の最短ルートがブロックされている時だけ。BFS の回数を抑制することで高速化を図った

花が目的地に選ばれる順番が序盤・中盤・終盤のどこに選ばれるかでベストな盤面が異なる。そのため、花の優先度が均等にばらけるようにシミュレーションのパラメータを調整した。
また、途中経過の成績が悪い試行については 20 回のシミュレーションを全て行わず、途中で早期に打ち切った

だいたい N の大きさに依存して数十~数百程度の盤面を試行できた


 5. やりたかったけどできなかったこと
 5.1 評価を高速にする最終的な解法は乱択に頼ったもので、重いシミュレーションによる評価でたまたま良いものが見つかるのを祈る、というようなものでした。

盤面を高速に評価できれば、より多くの盤面を試行したり、局所探索を適用でき、性能が上がることを期待できます。
高速な評価のために以下のようなことを試してみました:
全体のスコアは冒険者が花にたどり着くまでに何回左右の部屋を行き来したかで大体決まるとする
左右の部屋を行き来する回数は、各部屋の中にある階段状の構造物の数によって大体求めることができる
左右の部屋の間のパスの長さと左右を往復する回数の期待値をかけたものをスコアとして近似する
このような方針で高速な評価関数を作ってみたのですが、実際に試してみるとあまり精度が良くなかったです。

おそらく花の防衛機構のレイアウトの良し悪しについて評価できていないことが大きいのではないかと考えています。
最上位の方の方針をみているとこの辺りの評価関数をうまく作っていたので、上を目指すにはこの辺りをきちんと詰める必要がありそうです。

 5.2 インタラクティブのルールをうまく活かすこの記事で紹介した解法ではほとんどインタラクティブ要素を使用していません。

原理的に考えると、冒険者の動きをある程度観測してから遅延して木を置いた方が、情報量が増えているのでうまく置けるはず...なのですが、一体どのように扱えばわかりませんでした。
窮余の策として思いついたのが、以下のような配置をすることです:

冒険者の最初の移動が左右のどちらに行くかを見てから意地悪に木を配置して、無駄足を踏ませるというものです。6N ターン程度は必ず稼ぐことができるので良さそうな気がしますが、配置の条件が厳しかったり、パスの部分が長すぎたりするなどの問題があり、試すことなく諦めました。

 6. 最後にこれを読んで、「あまり難しいことやっていないのに 7 位が取れるの?」と思った方がいらっしゃるかもしれません。その通りです！
この記事に書いてあるように高度な発想はしていませんし(やりたかったのですが)、難しいアルゴリズムも使っていません。ビジュアライザを見ながら試行錯誤を繰り返し、挙動の改善を地道に行うことをやっただけです。AHC では(回によっては)ルールベースを突き詰めるだけで割と上位に入ることができることもあります。

(実際には挙動の改善の中で焼きなましを採用したりビームサーチをいい感じに採用しなければスコアが上がらない回も多いです。今回も最上位はそこをきちんと詰めて最適性の高い配置を見つけていました)
あまりかっこいい考察をしていないのに解説を出すのが恥ずかしいところもあったのですが、
地道に試行錯誤を繰り返すだけで割といい勝負ができることもある
実装・考察・改善というループを繰り返すことの面白さ
を伝えられればと思って記事にしました。もし読んで得られるものがあれば幸いです。
次のコンテストも楽しみですね! 次回も対戦よろしくお願いします!

脚注
また、社内の勉強会についても近いうちに記事がまとめられると思います。そちらも是非ご覧ください。 ↩︎