AHC054参加記：見せる木を工夫して見せないマスを作る
この記事はALGO ARTIS プログラミングコンテスト2025 夏（AtCoder Heuristic Contest 054）のユーザー解説記事です。私plasmaは63位でした。今回はちゃんと解説の記事です。
この記事の要点
- 上手く木で囲むとAAを隠せて発見を遅らせることができるよ
- でも冒険者は見えてる情報での最短経路で突っ込んでくるよ
- だから囲んでる木を見せることで最短経路じゃないことを知らせるよ
- 木の見せ方は色々あるよ
お断り
この記事では木とトレントと区別せず一律で「木」とします。「木を配置する」と書いてある場合はトレントを配置することとします。
また以下では画像での説明が多数含まれますが
- 白色のマスは木がないマス
- 灰色のマスは木があるマス、確認済みかどうかは問わない
- 黒色のマスは確認済みの木があるマス、範囲外の可能性もある
とします。
理想の見せ方
結論から言うと冒険者の認識が以下のようになればいいです(◯がAA)。
◯と✕のマスが目的地でない限りは最短経路になりえず、✕が目的地の場合も△のマスに到達した時点で✕のマスが確認済みになるので、◯のマスが直接目的地にならない限り◯のマスは確認されません。
なぜ認識が大事かというと、冒険者は確認済みマス以外は全て空きマスと仮定して行動するからです。例えば以下のパターンを考えてください。
△を冒険者、◯を目的地としたとき、冒険者目線では✕のルートが最短経路となります。すると次のターンに右に移動するため袋小路の中が確認済みになってしまいます。
というわけであの手この手で「ここは袋小路だよ」と冒険者に知らせるのが目的となります。
色々な見せ方
どのパターンでも「見つかる寸前までの道のりを固定して袋小路を演出する」が共通となります。
一般的なパターン
多くのケースではAAは森の内側にあります。色々アプローチはあると思いますが、私は大きく分けて以下の2パターンのどちらかで誘導できるかどうかを確認していました(実際には回転の4パターン×左右反転の2パターン分ある)。
見えにくいですが、△がついている木をどうやって見せるかがポイントとなります。◯が確認されず△が確認されるような誘導をすればなんでもいいのですが、真面目にやると場合分けなどが大変になるので、いくつかポイントを絞って十分条件で判定していました。
下の△の木を見せる方法
一番簡単なのは以下のパターンです。
内部に侵入するには✕のマスを通る必要があり、下の✕のマスを通った段階で△の木が確認済みになります。
他にも以下のような誘導があり、初期配置の関係でこちらを使う必要がある場合もあると思いますが、今回は実装できませんでした(気づいたのがこの記事を書いてる途中だからというのもある)。
あとはこんな形もあります。先に言っておくとこれは90度回転のパターンでは使えません。それを含めた詳細は後述。
残りの△の木を見せる方法
見せたい順番で誘導するルートも変わってきますが、以下の流れでルートを決定します。
- △のマスを見せるために通りたいマスを決める
- 通る順番を時計回りか反時計回りのどちらかかを決める
上の△の木
以下の✕のマスのうち、どれか1つを通ればよいです。
右の△の木
基本的には以下の✕のマスを全て通ればよいです。
なお上の△の木の条件を満たすために右のマスを選んだ場合は、こちらの一番上は通らなくてよかったりします(ここの場合分けを考え出すと沼にハマるので忘れてもいいです)。
左の△の木
基本は以下の✕のマスを全て通ることです。
ただしAAの下の空きマスが1マスで済む場合は左の△の木が存在しなくなります(最初の図を思い出すと袋小路に入ろうとした段階で認識されることが分かる)。
こちらでも上の△の木の条件の話が適用できますが、やはり面倒なので忘れてもいいです。
袋小路を組み立てる
通りたいマスと順番が決まったら後は袋小路を組み立てるだけです。今回使った方法は「実際の経路を算出して、各マスの四方に木を配置する」という方法です。実際の実装では「ここには置かないよ」というフラグで制御したりしました。
// 木を配置したい座標を渡し、まだ木がないなら配置、あるorこのターン配置する予定なら無視
void set_treants(int i, int j);
std::vector<std::pair<int, int>> route; // 経路
bool reserved[40][40] = {};
const std::pair<int, int> DIJ[] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
for (auto [i, j]: route) {
reserved[i][j] = true;
}
for (auto [i, j]: route) {
for (auto [di, dj]: DIJ) {
int i2 = i + di;
int j2 = j + dj;
if (0 <= i2 && i2 < N && 0 <= j2 && j2 < N && !reserved[i2][j2]) {
set_treants(i2, j2);
}
}
}
なお厳密な話をすると
- 袋小路の入り口などのブロックの設置をスキップする必要があるマスが存在する
- スタート地点から到達可能であることを確認する必要がある
- そもそも到達可能なマスが減りすぎると発見される可能性が高まり意味がない
などの注意点がありますが、詳しくは省略させていただきます。
以下他のパターンの袋小路の話をしますが、具体的な構築についてはこのパターンと大体同じなので丸ごと省略させていただきます。
四隅にAAがあるパターン
四隅にAAがある場合はもっと簡単になります。というのも範囲外の木は初期段階で確認済みという条件があるので見せるべき木が少なくなるからです。具体的には以下の形で条件を満たします。
そもそも四隅にAAが来る確率は0.5%ぐらいですが、単純計算で3000ケースあれば15ケースぐらい四隅に来るので、簡単に拾える点数は拾っていこうという話です。
ただし初期配置の関係でAAの下の空きマスが2マス以上必要になる場合は話が変わってきます。具体的にはAAの隣の木を別途認識させる必要があります。例えば次のパターンで困るわけです。
△のマスから✕のマスへの冒険者目線の最短経路を考えると、次のターンの移動は左となり、◯のマスが確認済みとなってアウトです。
これを避けるには真面目に誘導する必要があります。例えばこんな感じに。
✕の木が絶対認識されないですが、一応袋小路になってるのでやらないよりはマシです。
なお3マス以上必要になるパターンだとこんな誘導もあります。
縦方向に限定すると以下の誘導もあります(縦方向限定の理由は次の項で話します)。
ちなみにこんだけ書いといてなんなんですが、空きマスが2マス以上必要なパターンについて気づいたのがこの記事を書いてる最中なので頭を抱えています。まぁ何ケースあるのという話なので切り替えていきます。
左右の端にAAがあるパターン
四隅にあるパターンと同じく範囲外の木を利用できます。基本形は以下の通り。
一番上の木がいらない気がしますが、AAの斜め上に初期配置の木がある場合などは入り口を端にする誘導が必要になるので一番上の木が必要になります。端的に言えば場合分けを省略してます。
肝となるのは縦方向限定で使える誘導の配置です。具体的にはここ(上下反転版も載せておきます)。
冒険者目線の目的地への最短経路に灰色の木のマスが含まれている場合の動きを考えると、移動の優先順位が上下左右であること(問題文の処理6の部分を参照してください)から次のターンは✕のマスに移動します。すると灰色の木が確認されるのでここが袋小路だと認識してくれるわけです。
上下の端にAAがあるパターン
やはり範囲外の木を利用します。基本形は以下の通り。
やはり一番左の木が不要な気がしますが、左右の端のパターンと同じ理由で置いてます。
左右の端のパターンと違って✕の木が必要なことに注意してください。理由は先程と同じで移動の優先順位が上下左右だからです。以下の図の状況になると次の移動は✕のマスになります。
端にAAがあって四隅を利用するパターン
四隅の近くなら四隅を利用して省スペースにすることもできます。基本形は以下の通りです。
端の近くにAAがあるパターン
端が近い場合でも範囲外の木を利用できます。端から遠い位置から範囲外の木を利用しようとすると目的地に選ばれたらアウトのマスが増えるのでいい感じに閾値を定めていきましょう。私は
一般的なパターンに似てますが、下のマスの認識を考えなくていいのでその分スッキリしてます。一般的なパターンを組めなくてもこちらが組めることはあったりします。
万策付きたパターン
今までのパターンは言ってしまえば「冒険者に袋小路と知らせることができる強い袋小路」でした。初期配置の関係でどのパターンも適用できない場合があります。そうなったら諦めてとりあえず簡単な袋小路でも置いておきます。一応何もしないよりはマシっぽいです。
これすら作れない場合もあります。手詰まりです。悲しい。
なお上で紹介したパターン以外にも「強い袋小路」はあるらしいですが、そこまで思いつきませんでした。
余談1：袋小路を作ったあとの処理について
当然ながら袋小路を作ったあとも色々処理する必要があります。私は以下の処理を毎ターン繰り返しました。
- 今までに通ったマスかチェックする、通っていたら丸ごとスキップ
- 次の処理を上下左右それぞれで行う
- 冒険者から見て隣(袋小路が作れた場合)、もしくは2個先(袋小路が作れなかった場合)から順に見て到達できるマスを減らさず木を配置できるならそこに木を配置して処理を終了する、そのようなマスが見つかる前に木が見つかったら何もせず処理を終了する
- 袋小路が作れなかった場合はAAを隠すような処理をする
- AAの上下左右に冒険者がいて、冒険者からAAを隠せるマスがあればそこに木を配置する
- AAの四方のうち3箇所に木を配置した場合、残りの一方向でAAへの到達可能性を潰さない一番近いマスに木を配置する
- AAの上下左右と冒険者の上下左右で交差する点がある場合、その点からAAを隠せるように木を配置できる場合そこに配置する
経緯としてはこっちの処理が先で袋小路が後です。袋小路を思いついてからは絶対スコアで3倍ぐらい伸びました(順位も200位台から暫定75位最終63位まで上がった)。
余談2：目標スコアの設定について
相対スコア形式のコンテストでは各ケースのスコアの相加平均より相乗平均の方が指標として優秀らしいので、ローカルでのスコア比較では相乗平均を利用してました。
また各ケースの目標スコアを設定しておくことで「このケースではスコアが低いが目標も低いので諦めてよい」「このケースはそこそこスコアが出てるが目標スコアより遥かに低いので要改善」みたいなのが分かりやすくなります。そこで以下の方法で各ケースの目標スコアを設定しました。
- AAの座標より後の目的地のマスをチェック済みにする
- 目的地がAAの座標でない限り
(p_i, p_j) = (0, N/2) - 次の目的地がチェック済みならスキップする
- AAを通らない経路でチェック済みでないマスを通る回数が最小となる経路を01BFSで求める
- 経路の長さをスコアに加え、経路上のマスを目的地含め全てチェック済みにする
-
(p_i, p_j)
- 目的地がAAの座標になったら
(p_i, p_j)
AAの座標が早いパターンだと実践値の方が高くなったりしますが、大抵は実践値より高いスコアが出ますし、AAの登場が遅いほど目標スコアも高くなりやすいです。
参考記事：相対スコア AHC の立ち回り - Kiri8128の日記
終わりに
分かりやすくスコアが伸びる(そして理由も分かりやすい)袋小路法(仮)ですが、これが思いついたかどうかで大きく結果が変わったんじゃないかなぁと思います。他にも色々分岐点はあるっぽいのですが、一番分かりやすいのはこれでしょう。思いついてよかったです。
というわけでこの記事はここまでです。ここまで読んでいただきありがとうございました。
Discussion