🌳
AHC054振り返り

2025/09/29に公開
 はじめにALGO ARTIS プログラミングコンテスト2025 夏 (AtCoder Heuristic Contest 054)に参加した．最終的な順位としては200番ぐらいであった。

 問題と大きな方針問題がはじめ何のことかよくわからなかったのだが，冒険者に花が見つからないように木を植えていく問題．冒険者が「見えた」場所には木を植えることができないので，できるだけ視界を小さくするようにすること．後は歩数がスコアになるので，できるだけ「迷わせる」ことがポイントである．

 解法
 まず迷路を作ってみるプレイヤーは冒険者が1歩動く（1ターン）毎に木を植えることができるのだが，植えることができる本数に制限がないので，まず迷路を作ってしまうことを考えてみた．

迷路はできるだけパス数を長くすればいいと考えて，最短経路上に経路がなくならない限り木を植え続けるという形で迷路を作ってみた．ひたすら最短経路を潰していくイメージ．

最初に迷路を全部つくってしまう（seed = 0)
Seed 0から99までの100問の入力に対するスコアは53,771点であった．上の図は500点台の高得点がでている例であるが，これは冒険者の動きに依存した「たまたま」うまくいった例である．
冒険者は目的地を設定していて「見えている」情報だけで最短経路を進む．目的地に到達し，かつ最終目的地である「花」が見つかっていない場合は「見えていない」ランダムなマスを目的地とする．このため，最後の方で灰色で残っていた最初の方のマスを確認しに戻っているのである．よって，スコアを上げるためには，来た道をいかの戻らせるか？がポイントなのだと思う．

 迷路を2分割してみる迷路を左右半分にして，例えば冒険者が最初右側に進み，花にある程度近づいたところで右側の経路を遮断．スタートに戻させるようなことを考えてみた．

迷路を2分割する（seed = 0)
狙い通りにはできているが，seed = 0 のスコアはいまいち高くない．100問の合計は 72,967点なので上昇はしている．直前で道を塞ぎたいのであまり先の迷路まで作らないようにしているのもあり，迷路が直線的になってしまっている．
あと，右側を進んでいる途中で左側を目的地に選択してしまって戻るなどの動きもあったので，2分割は悪くないような気はする．ただ，Seed = 0の図のように「無駄な領域」ができてしまうのも事実である．逐次的に迷路を作るのはあまりメリットがないような気がしたので，最初に迷路を作る方式に戻す事にした．

 穴掘り法で迷路を作るこれまで，「できるだけ長い距離を歩かせる」ことを主眼に置いて迷路を作っていたが，脇道に誘い込んだ方がスコアがよくなりそうなので，普通の迷路作成アルゴリズムを使う事にした．普通の穴掘り法だと迷路の縦横の長さが奇数でないと動かないので，Growing Tree や Recursive Backtracking っぽいコードを実装してみた．壁が1マス使ってしまうので，無駄な領域ができてしまっている．

Growing Treeっぽい迷路（seed = 0)
いい感じに迷ってくれて，100問の合計スコアは183,833点．2倍以上高い．斜めに木を配置するのが良さそうである．アップロード時の順位で100位以内だったので，これベースに動的な処理を入れるといいのかな？とは思う．

 花が見つかりそうなら隠す迷路としては普通の迷路であるため，たまたま花が早めに見つかってしまう場合がある．そこで，花が見つかりそうになった場合は木を植えて隠してしまうことにした．

花の上下左右4つのマスを「木が生えてくるマス」として冒険者の目線に花が入りそうになった時に木を植えることにした．4つ全部植えてしまうと到達できないので，木を植えても到達できる場合に限定する．

花を隠す（seed = 7)
冒険者の動きとしては，移動する → (木を植える) → 周りをみる なので，移動した後に目線を確認して植えれば良く，実装は難しくはない．seed = 0だと変わらないので seed = 7を例示しているが，花に近づくと木が生えてくるのが分かると思う．100問の合計スコアは257,991点．アップロード時の順位で50番台まで上がった．実行時間としては100ms以下なので，時間を使って最適化すれば良いのかな？という気はする．

 スコアが低い問題に取り組んでみるseedを増やして1000問ぐらい作成してスコアが低い問題を探してみる．例えば以下の問題のスコアは16点．よくみると花の上下でエリアが別になってしまっている．このため上の小さいエリアしか使えないのである．
解決方法のイメージとしては色を塗って境界にある木を1本切ると2つのエリアをつなぐことができる．花を境に複数のエリアができることを想定して，花から最も遠い境界の木を1本切る事にする．
これで1504点まで上げることができた．同じような考えで右下の木が密集しているところも削除できたが，その時のスコアは1,468点だった．複数ケースの合計を見ても点数が下がっていたので，この処理は削除した．

100問の合計スコアは271,553点．少し増えているが，他の人のスコアも上がっているようで100番代まで下がっていた．

 迷路を評価する迷路の候補をいろいろ作る事を考えると，迷路の評価を行う必要がある．単純なのは冒険者の動きを模擬してスコアを算出することであるが，冒険者の目的地が乱数で決定されるので，そのまま求めることはできない．

スコアの推定値を実際のスコアの関係
そこで，目的地が最初から花の位置になっている最悪パターンと，乱数で目的値を求めるシミュレーションでスコアを推定したものと，実際のスコアの関係を求めてみた．結果としては上記グラフのような感じで，正直には厳しい．50回シミュレーションした平均を求めてみたが，それでも微妙な感じである．
2個迷路を作成して推定スコア（50回シミュレーションした平均）の高い方を採用するアプローチを取ってもスコアが上がらなかったので，実際の冒険者の位置をみながら変更していくのが大事なのだと思う．

 花に続く道を塞ぐ花を隠す事の応用として，壁を作る事を考えた．ある程度花に近づくと花に向けた最短経路を閉じる．その時花向きの経路がなくなった（2つのエリアに分断されてしまった）場合は，花から最も遠い2つのエリアに共通部分を壊すことにした．このため，迷路は最初につくっておくが，木を植えるのは視界に入った時という形にした．

動的に木を置くことでうまくいった例 (Seed = 63)
これは，これまで10ポイントしかとれてなかったSeed 10が316点とれたのでいい感じではある．ただ，100問の合計だと173,407点で10万点ぐらい低い．本番は相対評価だしなと思いアップロードしてみると200番台までに落ちてしまった．

冒険者が動くたびに迷路ができてくるのは，かっこいいのだけど，動きがわかりにくいのでデバックがしにくい．

 分岐の多い迷路にする他にスコアが低い問題を見てみると脇道が少ないので，目的地が異なるのに花に向かっていっている例があった．例えばSeed 17で80点しかとれていない．迷路の作り方としてひたすら掘っていって掘れなくなったら戻って掘れるところを探すという方法をとっているので，一本道ができやすいためであろう．

一本道に入ってしまった例 (Seed = 17)
そこで，迷路で分岐を増やすようにパラメタを変更してみた．スコアとして162点まで向上した．とはいいつつまだ無駄が多い．しかも，100問の合計だと67,723点と大きく低下．分岐が少ない方がそこを往復することで歩数を稼いでいるのだと思う．

分岐を増やした例 (Seed = 17)

 終わりにこの後，迷路を変更方法をシンプルにするために，最初に作成する迷路を単純にしたり，迷路で分岐を多くしたりしてみたが，あまりうまくいかなかった．動的な処理を入れるとデバックが大変なので，自前のビジュアライザを作ればよかったかなぁとも思う．そんな時間がなかったけど...