AHC054 参加記
はじめまして。今回初めて記事を書くに至った洋菓子です。
なぜ突然筆を執ったかと言えば、AHC054に初参加したら思っていたより好成績を修めれたから要するにうれしくてです。
初執筆なのでつたないところが多いですが、温かい目で見ていただけると幸いです。
AHC054 問題
提出
Submission #69725057 - ALGO ARTIS Programming Contest 2025 Summer（AtCoder Heuristic Contest 054）
はじめに
記事を書くとは言っても、何を書けばいいのか？と悩みましたが、とりあえずはどのようにして問題を解いたかについて簡潔にまとめようかと思います。
いったいこれがだれの役に立つのかは知りませんが、AHCってどういうもの？という人や、参加をためらっている人、緑以上のパフォーマンスを出せずにいる人などに向けて書かせていただこうと思います。
また、コードや考察はほとんどAI任せであったのでAIが好きじゃない方にはこの記事はあまりお勧めしません。
また、あくまで初めて参加してみてこんな感じだった！と言う感じの記事なので解説するものがないことは許してください。
ぜひとも初参加した私がどのようにして解いたのかをみて、興味を持ったらあなたもAHCに参加してみてほしいです。
長くはなると思いますが、どうかお付き合いいただけると幸いです…
1日目
私はこの10日間という長期AHCであったにもかかわらず、最終日4日前である9/26に初めて問題を見ました。
まず、問題文を見る前にAHC自体がどのようなものか自体は多少は知っていました。
問題文がとにかく長くて難しい
ということだけは聞いていたので覚悟はしていましたが...
これが本当に長くて理解しにくい。
幾度かビジュアライザで実際に木を置くなどして、何とかして問題を理解しました。
この時の自分なりの問題解釈
いくつかの障害物が既に設定された白紙の迷路があり、スタート地点とゴール地点が設定されている
冒険者はこの迷路をランダムに探索する(ある程度無駄を省いて)
このとき、冒険者が必ずゴールにたどり着けるが、到達まで時間がかかる迷路を構築してください
という問題
本来は迷路は一発で構築する必要はなく、冒険者の動きに合わせて設定できるが、問題設定的に初ヒューリスティックの自分が使いこなすには難しい、と感じたため基本的に一発で生成することをこの時点で決めていました。
さて、問題はある程度つかめました。
当然、理解が及んでいない点のほうが多いですかそれでも
まずはACして理解が正しいかチェックしよう
という教えをもとにACしてみることにしました。
しかし、ただ何もしないコードってのも…ということで、まずは貪欲法？などの簡単な手段から試すことにしました。
ここらへんで、AIはそもそも使えるのか…？ということが気になったのでルールを見てみたのですが
思ったよりも緩くてびっくりしました。
基本的にAIと一緒にコードを作るうえでは制限がないとのこと。
じゃあ、存分に使ってやろうということで早速問題を読み込ませてみました。
問題は、ただコピペするとTeXなどで書かれたものが消えるのでCtrl Uからhtml形式でコピペしてAIに読み込ませてみました。
最後までこれでやりましたが、そこまで悪いものではなかったと思います。
とりあえず、私ははじめにこの問題を理解したとき。
とりあえず長い道作ればそれが最高スコアじゃないの…？
と浅はかなな考えが出てきたので、とりあえずAIに依頼してスタート地点からなるべく長い道を辿り花に辿り着くような迷路を構築するコードから作りました。
しかし、意外とうまくいかないのがAI。ただ説明するだけじゃなく、多少実装方針を教えたらうまく生成してくれました。
普通のコーディングと同じようにAIにコーディングさせるには隅々まで説明しないと、細かいところは勝手に付け足してくれず融通が利かない…という感じで似ているなと感じました
とは言えもちろんAIなのでかなり勝手に補完して作ってくれるので、楽ではあります。
そしてコードを実際に実行すると、横にうねうねと伸びて最後に花にたどり着く道が生成されました。(成功までに5、6回程度やり直しました)
とりあえずこのコードで提出…ドキドキしながら待つと...57794得点。
アルゴリズム部門であんなに苦労している水パフォがこんなに簡単に出るとはと。
このとき本当にAI使っていいのか…？ともう一度ルールを確認してしまいました。
とりあえずACが出たので、次はどうやったらスコアが伸びるか？ということを考えることにしました。
そのために、AIに長時間解析でなるべく高スコアを出す迷路を構築させるコードを作ってもらいました。
しかし、これもやはりうまく行かず何も置いていないものが最適解と言い出される始末…
何度かAIと対話を繰り返し、最終的に30分ほど時間をかけて様々な手法から最高スコアを探し出すコードができました。
その時にできた最高スコアの迷路はこんな感じに。
ここでこのアニメーションを再生して、やっと問題をもう少し理解できました。
今まで冒険者の目的地決定や地図の確認済みマスについて何も理解していなかったので、ここでやっとよく読み直してみて理解しました。
つまりは、冒険者は未確認マスの中から適当に1つ選び、そこまで探検して花があるか確かめるということでした。
そしてそこから最高スコアを叩き出す迷路というのは
目的地への移動をたくさん繰り返させる迷路
構造であると言う検討がやっとつきました。
さすがにこのアニメーションのものぐらいのスコアを2s以内に出すものは難しいでしょうが、とりあえずはそういうものが最高スコアに近いものだということが知れたのでこれはかなり大きかったと思います。
今思えば問題的に明らかでしたが、このように実験を繰り返すことで色々な事実が明らかになっていくのはAHCの楽しさだと思いました。
ここまでわかったので、また明日…ということで1日目はここで終わりました。
2日目
さて、この日はABCがあった日でもありましたね。私はと言えば…
緑パフォですね…E問題で迷走して悲しかったです。
ということもあったので、気分転換だという心持ちでAHCを再開しました。
とはいっても、この日はそこまで進展せず、一度も提出はしていないです。
昨日の結果からどのようなものが高スコアになるかはわかったので、それを実際にプログラムが構築するには？ということに時間を割いていました。
そのためにはまず言語化してAIに伝えないといけないので、よくアニメーションを観察することにしました。
とりあえず、右上にいるときに左下の未確認マスが目的地になればかなり時間がかかりそうです。
であれば、一般にある時点で未確認マスがたくさん残っていればまだ花にたどり着くまで時間がかかる、ということで私は確認済みマスを増やしにくい迷路を構築することに重点を当てることにしました。
例えば、こういうまっすぐとした道とジグザクとした道であればジグザクとした道のほうがそのあたり全部を見るのに時間がかかりそうです。(要するに、見通しが悪い)
なぜなら途中に目的地があったとき、直線だとすぐに次の目的地に更新されますがジグザクならそこまで実際に行かなければ次の目的地が設定されません。
また、もしもジグザクの途中で別のとこへ目的地が変わったとしたら、その奥が未確認のままであり、次そこが目的地になればその道を2周したことになり、かなり時間が稼げるな…と思い、これは重要だろうという結論になりました。
また、花の近くが特徴的なL字型になっていることに気付きました。
これはなぜか少し考えてみたところ、もしもこのような場所に花があれば、花を確認するにはその隣にまで行く必要があり、これは周りに道が多い花に比べて、明らかに見つけにくくその分到達までに時間がかかり、高スコアに直結する要素であるのだとわかりました。
また、分岐が多く見られることにも気づきました。
はじめのようなただ長い通路を作っただけでは、基本的に一度目的地にたどり着くまでにほとんどの道を通り、一気に目的地の選択肢が狭まります。
一方で分岐がたくさんある迷路ならば、その経路分しか確認済みマスは増えず、さらに間違った道から同じ道を戻ることがあればその分だけ時間が稼げます。
よって、分岐をたくさん設置して花の周りはL字にして花を隠し、ジグザグな迷路を作ると言う方針に決まりました。
しかしながら、これを一度AIにどうでしょう？と投げかけたらいい方針ですね！としか返ってこなく、これを否定する意見は全くと言っていいほど返されませんでした。
AIはやはり基本的には人間がいい気分になる文を生成する傾向にあり、批判するようなものはかなり少ない気がします。
そこが少し使いにくい部分ではありましたが。
とにかく、この日はここまで分かったので少しAIにこの方針で迷路を作るコードを書いてもらいましたが…
これがなかなかうまく行かず、ここから詰まってしまいました…
特に苦労したのは、提出するコードへの入力とビジュアライザで用いる入力に大きな差異があったことです。
これはインタラクティブなのでしょうがないのでしょうが、せめて入力例はそのやり取りを入れておいて欲しかったです…
とりあえず一度ビジュアライザ用のコードで作り、最後に提出用に書き直してもらうことにしました。
3日目
用事があって疲れたので何もしませんでした。
4日目
さて、あっという間に最終日になりました。
ある程度先ほどの方針で迷路を作り出すコードを書けてはいましたが、なかなか正しい迷路を作ってくれなく、苦労しました。
何度も方針を伝え、それに沿っていない迷路やそもそも迷路じゃない何かができるたびにチャットを新規作成して余計なメモリを消したり、伝え方を変えたりなどの工夫をしてかなり高精度に作成してくれるものができました。
これである程度いい感じに迷路を作ってくれるコードが一度できたので、これを提出することにしました。
ここでビジュアライザ用から提出用に変換して提出…するとまさかの初回のコードよりも点が落ちてしまいました。
ここまで長々と考察したのにこれはショックでした。
原因を探ると、理由を見つけるのにそこまで時間は掛かりませんでした。
なんと今までのコードは本来非開示情報であるqlistを参照して評価していたのです。
一度「いや、やっぱqlistは与えられるのか…？」と愚かな幻想を抱き、qlistを使って評価するコードも提出しましたが、当然入力が来ずTLE。
何度も何度もAIに修正を頼みますが、ほとんどが同じ結果であっという間に時間は経ってしまいました…
正直、ここからは本当にうまく行かず苦痛でした。
ただ、何度もAIにコードの方針を伝えるうちにかなり理解が深まっていき、そこは面白かった点でした。
最終的にここからはほとんど考察を放棄して、私が気づいた最低限のことをAIに託してコードを作ってもらいました。
AIは少なくとも私よりヒューリスティックに長けているのは明らかなので、はじめからこれでも良かった気はしますが、とにかく局所改良や乱択やヒューリスティック的評価など、様々な手段を用いてAIは最終的にはじめの2倍のスコアまで押し上げてくれました。
中身を簡潔にAIにまとめてもらいましたが、
・AHC054 向けのワンショット解法で、元のグリッドから通路（.`）を残すようにマスを塞いでいき、入口から花（TI,TJ）までの最短距離を伸ばすことを目的にする。
・パリティ（隔セル）に基づく DFS で迷路を刻み、花から遠い方向を優先してジグザグな経路を作り、幅2以上の通路ができないよう隣接チェックで抑制する。
・花の周辺は「L字」構造を意図的に作って花を隠し、花へ入れる隣接を1方向に絞って遠回りさせる処理を試みる（失敗時はフォールバックで最低限の接続を確保）。
・最後に時間制限内にランダムな開閉セルのスワップを試す局所改善を行い、常に入口⇔花の連結性を保ちながら最短距離（スコア）を向上させる。
・複数候補を乱数で生成してベストを採用し、失敗時は安全なフォールバック（元グリッド）を返す実装になっている。
という感じのようです。
しかしこれでもあまり順位は上がらず、かなり改良したと思いましたが青パフォには全く届きませんでした。
できた頃はより改善しなくては…という感じでアニメーションの観察を怠っていましたが、よく調べてみるとただ複雑化しただけのはじめの最長経路構築とほぼ一緒なことに後で気づきました。
それまでは、多少方針を自分も考えていましたが、ここからはこのコードをスコアをよりよく得られるように改善してください！だったり、抽象的なプロンプトが増えた気がします。
さすがにここまで来るとビームサーチだとか焼きなまし法だとか聞いたことしかないものに頼る必要がありそうで、それを知らないなら仕方ないとえば仕方ないとは思いますが効率は悪かった気がします。
また、やはり毎ターンごとに迷路を作れるのだからこれを利用しない手はないと思いそのような方針も抽象的に頼んでAIに作らせましたが、あまり手応えは得られずすぐに諦めました。
なのでそのあとはまた、AIに改良させ続けていったのですがなかなか良いものはできませんでした。
しかしいくら改良しようとしても改良できず、もう一度アニメーションを観察したところ、qlistを参照したものに比べて迷路の分岐が少なく、結果的に先ほども述べたように最長経路を構築しているのとほぼ一緒なことにやっと気づきました。
よりスコアを伸ばすには、どちらかというと、右のような大きな長い幹があり細かい枝があるような迷路より、左のような真ん中に全体の枝が集まっており、ある地点からある地点の移動をする際に余計なマスを確認させない構造のほうが強力なことに気づけました。
しかしこの時点でその後に予定が入っており、すでに時間はありませんでした。残り少ない時間で多少はその旨をAIに伝えコードを書いてもらいましたが、どれも迷路とは言えないものになってしまい、結果も全くもって良いとは言えませんでした。
ということで、最終的にはこの100000スコアとれたコードで私の初AHCは幕を閉じました……
参加した感想
まず、AIの恐ろしさを感じました。
初参加であるのにもかかわらず簡単に水パフォが出せたのは、さすがに恐ろしいです。
やはり今後は、生成AIがプログラミングの大半を担っていくんじゃないかな～と思ってしまいました。
実際、中身のそもそもコードが何をしているか結局全く知らないですからね。
次にAHCの感想ですが、結構楽しかったです。
現在私はJOIに向けて精進しており、そのうえでヒューリスティックは別にいらないかな...と無視していましたが、急にAHCが目にとまったので参加しました。
実際AHCのビジュアライザとか見て、面白そうだな～と思っていたので参加できてよかったと思います。
それに、何回も実験して一つの問題にいろいろ理解が深まっていく過程はかなり面白かったです。(まだまだ考察は浅いですが)
ぜひとも様々な人の解説や解法を見させていただき、ヒューリスティックのほうも少しずつ精進できたらいいなと思います。
それでは、またいつか暇ができたらブログを書き込みに来ようと思います。
次はそうですね...アルゴリズム部門が水色になったら書きに来たいと思います。
