AHC054参加記録 with Claude Code

はじめに

ALGO ARTIS プログラミングコンテスト2025 夏（AtCoder Heuristic Contest 054）に参加して、暫定21位→システムテスト32位でした。

AHCの参加記を書くのは初めてですが、学びが多かったので勢いに任せて書こうと思います。特に今回はLLMをフル活用して実装を進められました。

ほかの参加記は解法寄りのものが多い印象ですが、本記事ではコンテスト中の思考や工夫点をうまく伝えて、AHCに興味を持ってくれる人が増えると嬉しいです。

問題

  • 盤面の中の花が見つけないように木を配置する
  • 冒険者が花を見つけるまでにかかるターン数を最大化したい

全体的な方針として考えたこと

  • かくれんぼのような問題
  • インタラクティブに木を置いていくのは難しいと考えたので、なるべく移動距離が長くなるように盤面を構築したい
  • 必要なターン数は「盤面の往復回数 × 往復距離」なので、なるべく往復距離を稼ぎつつ、隠れている目的地を増やして往復させたい

どんな盤面が良い？

最初の3〜4日間は、どんな盤面が強いかを考え続けていました。なかなか良いアイデアが浮かばず、つらかったです。

最初の数日は外から内に向かう渦巻きを構築して、外側にL字をたくさん作れば良いのでは？と考えましたが、実装が大変で諦めました。

試行錯誤する中で、ビジュアライザの入力を改造すれば、作りたい盤面がどの程度のスコアになりそうか見積もれることに気づきました。

ジグザグに上下へ移動しつつ、端側の道に長さ2〜3の枝分かれを作ると、良いスコアが出やすいと分かりました。

いざ実装？

上の方針で盤面を作りたいものの、木の障害物も考慮した配置は難しそうです。さらに、花に到達しないように木を配置する必要があり、その点も検討が要ります。

試しにLLMに「このような盤面を構築するアルゴリズムを考えて」と依頼しても、筋の良い解法は出てきませんでした。

そこで、まずは手作業で構築するとしたらどうするかを小さく実験し、それを参考にしながら構築手法を考えました。

仕様を可能な限り細かく分解する

手作業の実験から、ざっくり次の手順で構築するのが良さそうだと分かりました。

1サイクルにかかる時間はそこまで重くないはずなので、ランダム性をある程度持たせて多様な盤面を生成し、10~500回程度回して最も有望な盤面を返すようにしました。

Step1: 先に花を良い感じに囲っておく

こんな感じの花に対する木と道の配置方法を８パターン作り、配置可能なパターンをランダムに選んでおきます

Step2: 左右の道を作る

左2〜3列は後で分岐を作りたいので空いた状態を保ちつつ、上から下に伸びる道を作ります

道の生成は最初はDFSで頑張っていましたが、途中でDPベースの構築に切り替えました（i番目の列にいるときに、どのj番目からi+1番目に移動するか）。

右側の道については、盤面を左右に反転させれば同様の実装を使いまわせます

Step3: 左側から右側に向かう一本道（メインパス）を作る。

Step2で作成したDPを応用して経路を生成します

左側の道の上端から出発し、下端に到達したら盤面を上下反転して折り返す操作を、右側の道に接続するまで繰り返します。

Step4: 一本道とスタート地点・一本道と花をつなぐ道路を作る

Step5: 左端の道と右側の道に分岐を増やしていく

スタート地点から遠い順に、メインパス上で未舗装の周囲セルに分岐を伸ばします。 その際、分岐が他の道へ不用意に接続しないよう注意します

Step6: 後処理

道にならなかったセルに対して、一部を道に、一部を木にします。

Step7: 盤面評価

ローカルテスターの実装を基に、花の巡回順を仮定して必要ターン数を見積もりました。花の出現順によるばらつきを抑えるため、花は最後に出現する前提としました。

個々のステップの実装方法を明確にする

方針が定まったので、ステップごとにどの手法で実装するかの方針を立てました。

目的と目指したい状態のイメージを共有したうえで、LLMと壁打ちしながら仕様書を作成しました。

Claude Codeは早く実装したくなりがちですが、仕様の認識を合わせつつ、バグが出にくいと判断できるまで対話を繰り返しました。

このように、doc/配下に各ステップの仕様書を可能な限り細かく作りました。

テストを作ってモジュール単位で結果を確認できるようにする

仕様書を作り、LLMにコードを生成させても、LLMの実装が間違うことはあります。

長期AHCはパイプライン全体が完成しないとWAになるだけで、どの部分が間違っているのかを特定するのは難しいです。

そのため、実装をいきなりLLMに全投げは難しくかつ確認が大変であるため、部分ごとにモジュール分けしてテストを確実に進めながら実装する方針を取りました。

（テストの例）

実装の中身はほぼClaude Codeに作ってもらっており、得られたコードを人間がテストしてあっているかどうかを確認する作業をしていました。Claude Codeが実装している間は他の作業もできるので、人間とAIで分担して進められます。

また、私はPythonの読み書きには慣れていますが、C++はあまり慣れていないため、まずはPythonで作って結果を確認しながら進めるようにしました。

全部のコードを繋げる

モジュールができ上がったら、それらを繋げます。これは部分ごとに作ったモジュールを組み合わせるだけなので、LLMに任せてもバグは比較的少なく進められました。

PythonからC++への変換もClaude Codeに手伝ってもらいました。そこそこの解が得られたのが7日目あたりになりました。

解の改善

盤面をデバッグ出力しながら、スコアが伸びる盤面・伸びない盤面を見比べて微修正を繰り返しました。pahcerがとても便利で、活用していました。

（デバッグ出力の例）

工夫した点として、盤面の評価のシミュレーションが重く、数十盤面しか評価できなかったため、なるべく有望な盤面を優先的に評価しました。

特に、花が一本道の途中に置かれているとき、花の周囲に未確認セルがあるとショートカットが発生して大きくスコアが下がるため、

スタートから花までの最短パスを見た際に、花の周囲の未確認セルが少ない盤面を優先的に評価することで、ある程度リスクを回避しました。

LLMに任せた改善

問題設定・解法・現在のコード・pahcerの使い方をまとめたうえで、CodexやClaude Codeにスコア改善をお願いしてみましたが、やはり効果は限定的でした。

一方で「このモジュールのこの処理を高速化して」「この処理に多様性を持たせて」など、ピンポイントな指示は比較的うまくいくことが多かったです。

LLMに実装を任せることで1回あたりの試行時間を短縮でき、トライアル＆エラーの回数を多く回せたのは良かったです。

終わってみた感想

長期AHC（特に直近のAHCはValidの解を出すのが難しい）は実装が重く、子育てとの両立も難しいため、AHC040以降はあまり参加できていませんでした。

それでも今回は、LLMの力を借りることでマラソンを走り切ることができ、良い経験になりました。

ただし、LLMに頼りきりでは（短期AHCならともかく）長期AHCは厳しく、適切に方針を指示しないと良い解にたどり着けない、という学びも得ました。仕様駆動設計というものがあるらしいのでそのうち勉強してみたいです。

仕事でも同様にClaude CodeやLLMを使っており、職場の詳しい人に教えてもらっているので、今後もさらに良い活用方法を模索していきたいと思います。