AHC054 参加記 & 1位解法解説

最近参加していた ALGO ARTIS プログラミングコンテスト2025 夏（AtCoder Heuristic Contest 054） でなんと優勝することができたので、X に書ききれなかった細かい工夫点などを含めた参加記と解説を書いていきます。

Heuristic Contest の概要は以前も書いたので割愛して、問題の概要と考察・解説から始めていきます。

問題

与えられたフィールドである森に木の魔物（トレント）を生やして迷路を作り、森の中に咲く花を目指して探索する冒険者をできる限り邪魔して長い間森に留まらせる問題です。

詳細はコンテストの問題ページを確認してください。

重要な点は以下です。

• N\times N のグリッドがあり、いくつかのセルには元々木が生えている。また、ある特定のマスには花が咲いている。冒険者はこの花のあるマスに辿り着くことを目標に森を探索する。

• 冒険者は 1 ターンに 1 マス移動できる。あなたは、冒険者が移動する様子を見て、好きなタイミングで空きマスに木の魔物（以下、区別が必要でない場合は単に木）を生やすことができる。

  • ただし、一度でも冒険者に視認されてしまったマスには木を生やせない。
  • 冒険者の視界は上下左右に伸び、木によって妨げられる。

• 冒険者の位置から花へは常に到達可能でなければならない。

  • そのため、最終的には冒険者が花に到達してゲーム終了となる。ゲーム終了までに冒険者が歩いた歩数がスコアとなる。

• 冒険者は、視認した木を地図に書き入れながら探索を進める。

  • 冒険者は状態として目的地を持ち、常に現在の地図上の最短経路に従って移動する。
  • 次のような場合、目的地を変更する。
    • 目的地に設定されたマスが冒険者に視認された場合
    • 目的地が現在の地図上で到達不可能であることが判明した場合
    • 花のあるマスを視認した場合
      • この場合は以降花のあるマスが目的地となり、花まで最短距離で進んでゲーム終了となる

• 目的地を変更する場合（または最初に目的地が選ばれる場合）、冒険者が視認していないマスの中から、現在の地図上で現在地から到達可能なマスを一様ランダムに選ぶ

というわけでかなり複雑なルールですが、どうにかして冒険者にできるだけ長く歩かせる必要があります。

考察

インタラクティブに解くか？

この問題はインタラクティブ問題で、冒険者の動きに合わせて動的に木を生やすことができます。情報をフルに活用することを考えると、今までの冒険者の行動から現在の冒険者の目的地を推定して、それに合わせて迷路を作ることなどができそうです。

しかし、よく考えてみると、次の目的地の大まかな場所が分かったところであまり嬉しくないということが分かります。どちらかというと冒険者の現在位置の方が重要です。そして、「どの位置に来たときに何が見えるか？」という問いのほとんどは、事前に迷路をデザインした段階で答えられることが分かります。

すなわち、「この位置に来たときにはこうなってほしい」という要求が適切に組めるのならば、そのほとんどは迷路を設計した段階で満たすようにできるということになります。

結局、事前に迷路を設計しておく方針でも、最適ではないかもしれないが、十分良い解は得られそうなことが分かります。インタラクティブに解くとなると考えなければならないことが増えるため、ひとまず事前に木の配置を全部決定する方針で進めることにします。

仕様変更のアナウンス

そうこうしているうちに、運営から次のようなアナウンスが入りました。

打ち切り出力: 新たにトレントを配置するマスの集合を上記の形式で出力する代わりに、-1 のみからなる行の出力を行い、プログラムを直ちに終了しても良い。
その場合、それ以降は m=0 の出力が冒険者が伝説の花を見つけるまで続いたものとして処理され、また、Tester がその処理にかかる実行時間は実行時間制限に含まれない。

インタラクティブ性を捨てて終了を宣言する出力をした場合は、その後の冒険者の探索ロジックにかかる計算時間は実行時間制限から除外されるとのことです。

実は単に処理が楽になるだけでなく、冒険者の探索処理にはテスター側で最悪数百 ms 程度かかることもあるようで、案外馬鹿にならないアドバンテージを獲得できることになります。

このアナウンスを見てインタラクティブ性を捨てて解く決断をした人も多かったようです。

見られない行き止まりを作る

この問題で最重要となるのが、どれだけ冒険者にとって既知のルートを何度も往復させられるかという点になります。

冒険者は視認したマスを目的地に選ばなくなるので、どれだけ長い迷路を用意しても、一度全て探索済みになってしまえば二度とその迷路に入ることはありません。

しかし、次のような構造の場所を作ると、水色のマスが目的地に設定されていない限り、冒険者は水色のマスをスルーして次へ向かいます。

これは、冒険者の持つ地図上でも水色部分が袋小路になっていることが分かるので、行っても無駄であることが事前に分かるためです。

しかし、未探索であることには変わりないので、後に水色マスが目的地に選ばれたとき、冒険者はここまで引き返してくることになります。

このような場所をたくさん作っておけば強そうということが分かります。

しかし、テストケースによっては画像のようにかなりの本数の木が元から植わっており^[1]、スタンプのように構造を埋め込んでいく方針だとこれらが猛烈に邪魔です。

というわけで、どうにか道の作り方を探索しながらこうした行き止まりを作れないか考えます。

袋小路を評価しながら焼きなまし法で道を作る

自分の解法の中で最も重要かつ特徴的な部分です。

とりあえず道に沿って木を全部植えることを考えます。すると、冒険者が通る予定のパスの両脇に木が植わることになります。

丸が元から植わっている木、四角が自分で植える木です。黄色はその木が冒険者に視認されたことを示します（自分で植える木は、冒険者に視認されるまで表示していません）。

植えられた木の中で、橙色のものに注目してください。この色の木は特別なもので、この木を冒険者が視認することでその時点の冒険者の地図上で閉じられた空間が発生します。

したがって、このような木を最後に撤去する（＝植えないことにする）ことで、先の画像で示したような未探索マスからなる袋小路を作ることができます。

このような木は、実は局所情報を見ることで定数時間で判定することができます。

木が袋小路を作ることの判定

まず、判定したい木の周囲 9 マスの情報を取ってきます。中央のマスに植える木が判定対象です。

次に、中央の木よりも先に視認される木を全てマークします。図では黒く塗りました。

このとき、中央のマスを黒く塗った場合に白い領域が二つ以上に分断されるなら、中央の木は袋小路を塞ぐことが分かります。なぜなら、視認された木は道に沿ってずっと並んでいるので、残りの領域が分断された時点で少なくとも一つの領域は木に囲まれていることが保証されるからです。

結局、次のようなパターンのときに中央の木が袋小路を作ることが分かります。

ただし、グレーのマスは白・黒どちらでもよいことを、青のマスは「それらのうち少なくともどれか一つが黒である」ことを表します。

袋小路の「良さ」の判定

道中にできた袋小路がどの程度良いかを、「後からその場所に何回訪れそうか」で数値化します。

例えば上のような構造になっていると、未探索マスが 1 マスしかないので、どうやってもあと 1 回しか訪れてくれません。

では、こうなっているとどうでしょうか？

2 マスあるので 2 回……とはならずに、期待値としては 1.5 回となります。これは、奥のマスが最初に選ばれてしまった場合には、全てのマスが最初から探索されて終わってしまうためです。

同様にマス目をジグザグに伸ばしていった場合を計算すると、未探索マスの個数を n とすると訪問回数の期待値 E_\text{visit}(n) が

E_\text{visit}(n) = \sum_{i=1}^n \frac1i

で求まることが分かります。これは対数オーダーで増えていくので、袋小路を大きくしていくのは途中から効率が劇的に悪くなることが分かります^[2]。

上の画像の場合は1+1/2+1/3+1/4+1/5+1/6=2.45 なので、平均して 2.5 回に満たない、ということになります。

そこで、1 手で同じ方向に好きなだけ直進できるような BFS を使って袋小路の入り口から最奥部までの距離を計算したときに、その距離までの逆数の和をもって袋小路に訪れる回数の期待値、とすることにしました。

実際のところこの評価は少し悲観的すぎたようで、未探索エリアのマス数に 0.01 を掛けて足したところスコアが伸びました。

焼きなまし法の評価関数

「各袋小路に平均して何回程度訪れそうか」というのが分かると、最終的に冒険者がどれだけ移動することになりそうかというのを見積もることができます。

というのも、「目的地が変わる瞬間にどの袋小路にいるか」と「どの袋小路内のマスが次の目的地に選ばれるか」は、いずれも概ね「その袋小路に訪れる回数に比例して大きくなる」と考えることができる^[3]ため、全部の袋小路間のペアに対する距離の重み付き和を計算することで、未探索マスを使い尽くすまでの冒険者の平均移動距離を見積もれます。

具体的には、袋小路 i の期待訪問回数を n_i、袋小路 i, j 間の距離を d_{ij} とするとき、

\dfrac {\sum_{i} n_i\sum_j d_{ij} n_j}{\sum_j n_j}

のような式になります。実際はこれをベースにパスの長さなどを加えて少し加工したものを用いました。

袋小路の個数は精々数十個程度で、定数倍も軽いので毎回 O(n^2) で計算してしまいましたが、大きなボトルネックにはなりませんでした。

状態遷移

この手のパスを探索する焼きなまし法では典型的な、一部をランダムに切り取ってランダム DFS で繋ぎ直す遷移を採用しました。

それぞれの木には「パスのどの時点で観測されたか」を配列で記録しているのですが、これを受理されるたびに全て書き換えていると遅いので、パス上のセルに double 型で時刻を割り当て、切り取った部分で時間を等分配することで全体の更新を避けました。

ただし、時刻が指数的に引き延ばされて精度が足りなくなる危険性があるため、100 回受理されるごとにパス全体の時刻を計算し直しています。

その他の工夫

以上が焼きなまし部分の解説ですが、他にも重要な点がいくつもあるので、それぞれ解説します。

花を死守する

花は「花があるマスが目的地に選ばれない限り絶対に観測されない」ようにしなければなりません。この条件が守られないと、そのケースでの得点の期待値が壊滅的に悪化します。

どの程度悪化するのか見積もってみましょう。

目的地に選ばれると花が観測されてしまうマスの数を m 個とします。条件を満たしている場合、花のマスだけが対象になるので m=1 を満たします。

このとき、導出は省きますが、目的地の候補をランダムに選択していくと、そのようなマスが最初に選ばれるのは、平均して全体の候補のうち 1/(m+1) の割合が選ばれた後になります。

直感的には、数直線上の [0,1] の範囲にランダムに点を m 個バラ撒いたとき、最小値の期待値が 1/(1+m) になるから、と理解できます。これは、点を等間隔に配置したときの値に一致します。

したがって、m=1 の場合のスコアを 100% とすると、m=2 になってしまった時点で 2/3、すなわち 67% しか得点できなくなってしまうことになります。

最上位は数 % の差を争っているので、こういうケースが無視できない個数生まれてしまうと致命的になります。

自分の場合は、花を迷路の末尾に配置していたので、こうならない条件は以下のようになります。

色のついた道が迷路のパス、白丸が花です。

まず、花の直前のマス (B) で曲がっていることです。そうでないと、花の直前のマスが選ばれたときに最後の直線部分に進入してしまい、花が発見されます。

次に、画像に示した ①～③ のマスが、花の二つ前のマス (A) に到達した時点で全て冒険者に視認されていることです。これらのうち一つでも視認されていないマスがあると、それらが目的地に選ばれたとき、冒険者がマス B まで進んでしまい、花が発見されます。

花はうまく隠しつつも、見せる必要のあるマスはきちんと見せなくてはならないというのがこの問題の難しいところでした。

運悪くこれらのマスが視認されないような配置になってしまったときに、植える予定の木を何本か撤去することで目的のマスを視認させることができる場合があります。

例えば上のようなケースがあったとします。パスは青から始まって赤に繋がっていて、終端に花があります。

終端付近を拡大したものが上です。灰色の四角は、元々植える予定だった木、ピンク色のマスは、元々は視認されるべきなのに視認されなかったマス（前の画像の ①～③ に相当）を表します。

このとき、灰色になっている木を撤去することによって、ピンク色のマスを冒険者に確実に視認させることが可能になります。

このような判定は頑張ればほぼ定数時間でできる^[4]ので、焼きなまし法のスコア関数に組み込んでしまいます。

同時に、目的地に選ばれるとゲームが終了するようなマス目の個数を計算し^[5]、スコアを減衰させることで、そのようなマス目を一つでも減らすように探索が進むようにします。

他にも、いくつか木を撤去することで惨劇を回避可能な例を挙げておきます。

盤面を分断する

コンテスト終盤前あたりまで入口から一本の長いパスを作る戦略で頑張っていたのですが、この辺りでどう頑張っても 1 位のスコアに到達できなそうなことが判明します。

細かいところを詰めれば数 % 程度は伸びるかもしれませんが、この差を埋めるのは無理です。ということで根本的なアイデアを見直します。

よく考えてみると、一本道を辿る過程というのは無駄が多いということに気付きます。先の計算結果を見ると、例えば長さ 200 の一本道を辿る過程では、平均して \sum_{i=1}^{200} 1/i=5.878\dots 回程度の目的地の変更が行われているはずです。

このとき、道の中央付近から辿り始めて、目的地が変更されるたびに両端を往復するチャンスがあれば、それだけでかなりスコアが伸びるはずです。

ただし、冒険者は地図上で目的地までの最短経路を辿ろうとするため、今まで歩いてきた道を全部引き返させるには、その道が最短経路になっていなくてはなりません。手っ取り早いのは、「引き返す以外に道がない」ことを冒険者に分からせることです。

引き返さなくても行けるかも…？

引き返すしかなさそう

というわけで、入口が道の中央付近に来るようにして、できるだけ早く両端を森の反対側に到達させたあと、残りをクネクネさせるという方針に変更します。

実際やってみると、ここでも木がものすごく邪魔で、しかも花がど真ん中にあったりするとうまく避けないといけなくて、ルールベースでの構築が大変難しかったです。

そこで、ビームを撃ってしまうことにしました。解を見つけること自体はそこまで難しくないので、ビーム幅はあまり太くなくても大丈夫そうです。候補も色々増やして、

1. 入口から左に行って分岐し、右下へ伸ばす
2. 入口からすぐ分岐して下に伸ばす
3. 入口から右に行って分岐し、左下へ伸ばす
4. 盤面を ±90 度回転させて 1.～3. を試す^[6]

としました。評価関数は「面積を均等に分けられているか」「2 つのパスが離れていないか」「移動がジグザグになっているか^[7]」などを組み合わせたものを用いました。

さらに、運が悪いと両側の道を伸ばした時点で木に囲まれていてそれ以上伸ばせなくなることがあるので、その後道を長くすることだけを考えた焼きなましを少しだけ走らせることで、詰んでいる候補が選ばれるのを防ぎます。

初期の道の探索とその後のメインの焼きなましの過程

袋小路に木を追加する

たまに大きい袋小路ができることがあります。このとき、内部に木を追加してやると、使用回数の期待値を 1～2 回程度増加させられることが多いです。

木を追加する箇所は袋小路内の冒険者の動きのシミュレーションをランダムに 50 回行うことで評価しています。領域が狭いので高速で、各袋小路で 200 反復の焼きなまし法を回せました。

これはかなり効果が高く、最終日前日あたりでさらに数 % 程度スコアが改善しました。

未使用の領域を解放する

ダメ押しの一手です。

色々な理由で袋小路にはなれなかったものの、木を撤去することで近い役割を果たせそうな場所を判定して、木を撤去します。

1% 程度スコアが伸びました。数値的にはそこまで大きな改善ではないですが、最終盤での 1% は重いです。

例えば上で点滅している木は撤去したところで袋小路にはなりません（冒険者が左上から右下に進むため、途中の地図上で袋小路になっていることが分からない）が、目的地が右上にあった場合はスルーして進んでくれるので、開けておいた方が得です。

おわりに

今回はスコアのブレが非常に大きいので暫定順位があまり当てにならずビクビクしていましたが、コンテスト終了後のシステムテストで無事 1 位を獲得することができました！

最近長期のコンテストで思うように結果が出せていなかったので嬉しい限りです。

なぜかニュースに

https://t.co/1vZ5BtgCyz

— ゴジラ＠競プロ (@gojira_kyopro) October 1, 2025

なぜか Grok による自動トレンドまとめでニュースになっていて笑いました。スポーツカテゴリになってるのは嬉しいですね（？）

実は毎回まとめられてるとかありそうなので、コンテスト終了後は気を付けて見るようにしてみます。

改めてコンテストを開催してくれた ALGO ARTIS さんありがとうございました！　懇親会も楽しみにしています。

追記

@shr_pc pic.twitter.com/KWfLBI9RcN

— あしぃ (@asi1024) October 13, 2025

抜かれました。

この差はもうちょっと本質的な改善が必要そうに感じます。

思い当たるところとしては「入口での分岐を除いては末尾まで完全に分岐がない」というのがあり、焼きなましの探索過程を改造して終端近くでは分岐した木を生やすようにするなどすると戦えそうな気がするんですが……まあまあ大きな変更が必要で延長戦バトルする気力が足りていません。うーん厳しい！