カエルの競プロ日記

カエルの競技プログラマーkeroru10の日記です

AHC052参加記

AHC052にChatGPTのCodexを使ってVibe AtCodingで参加し、11位になりました。今回も自分では一切コードを書いていません。
今記事ではコンテスト中の立ち回りについて書いてみようと思います。

AHCでのCodexの活用法についてはqiitaにまとめています。 qiita.com

問題

M台のロボットでN×Nマスの全てをワックスがけしたい。K個のボタンがあって、それぞれのロボがどう動くかは自由に設定できる。 atcoder.jp

解法要約

  • 1台を代表ロボとして「盤面を舐める巡回路（TSP風）」を作り、代表がその前半X%を塗り終わる間に後半Y%の未到達マスを新規に塗れる数が多くなるように他ロボの方向キー割り当てを44の256通りから貪欲に選んでいく。
  • X、Y、代表ロボ、他ロボの割り当てを決める順番、の組み合わせを変えて最善を探す。
  • 残ったマスは代表ロボが塗るが、近いロボへ引き継いで短縮できるなら短縮する。

ロボットの動きは独立に決められるので、ボタンの押し順を先に決めてしまって後から最善の方向に割り当ててやればいいというのが今回の勝因になった閃きでした。
あまり似た方針の人は見かけませんでしたが、結果的に今回の上位方針である各ロボを初期配置してヘビ状に塗るという動きになっています。

-0:15

GitHubにリポジトリを用意してAGENTS.mdの高速化TIPSなどをアップデートする。

0:00

GPT-5 Pro(以下、5P)をいくつか開き、問題を貼って解答方針、部分問題への分割、有効なアルゴリズムなどを考察するように質問する。
（最近、半端に賢くなってコンテスト中は助言はできませんとか言いよるので生成AIルールのページへのリンクも貼るようにしている。）

0:01

リポジトリに問題文、入力ケース、公式ツールをアップロード。

0:05

自分でも問題を読む。つい先日のAWTFの問題が頭をよぎる。

0:08

とりあえずテスト環境の構築(スコア計算とローカルテストプロセスの実装)と自明解の作成をCodexに投げる
srcも参考にしてcompute_score.pyを作成せよ。また、ACをとれるa.cppを作成せよ

5Pの返答が返ってきたので読む。
いつにも増して参考になる方針がなく、自力考察もいい案が浮かばず軽く絶望する。焼きなましよりはビムサかと思ったが、ビムサだと相当うまくやらないと隙間が残る塗り方をしそうなので焼き方針で粘ってみる。
5Pにもどうにかして焼きなましで解く方法に落とし込んでと聞いてみる。

0:20

Codexの環境構築が終わったのでPRをマージして2個目の指示
a.cppを改善せよ。ランダムでボタン設定して、一つのロボに注目して全マスを塗れ

0:25

5Pの焼きなまし案を読むが碌な案がない…。移動方法を焼くのは無理がありそう、ボタンなら焼けるか？？

0:32

Codexが作業完了したので提出する。 スコアは135300。0番で全マス塗るようDFSでしてるようで行ったり戻ったり無駄は多いが一応、全部塗れている。 無駄が多すぎるのでとりあえず1台にTSPしてみるようCodexに指示
a.cppを改善せよ。ランダムでボタン設定して、一つのロボに注目してTSPで全マスを塗る最短を出せ。

0:41

TSPができたのでとりあえず提出しつつ、コードテストで流すと実行時間3ms。えっ…お前絶対TSPしてないじゃん…。とはいえ、Visualizerで見てみるとジグザグにヘビ状に塗りながら効率よく塗れている。
スコアは258688。

0:48

やっぱり短期コンは天才貪欲か？と思い始める。過去改変貪欲的なやつ使えないかなーと考え出して、ここで天啓が降りる。
ボタン先に決めようとするから難しいんであって、後からいい感じに塗れてたことに改変すればいいじゃん！
5Pに壁打ちしたらよさそうなのでCodexに指示
a.cppを改善せよ。一つのロボに注目してTSPで全マスを塗る最短経路をまず出す。次に、経路の長さの1/3まで塗る動きに対して、残りの各ロボットに対して4^4パターンのボタン割り当てそれぞれであったと仮定した時に、TSP経路の後ろの方から長さ1/3のマスの内、塗れる新規マス数のもっとも多いパターンを貪欲に割り振っていく。前のロボットが最大効率で塗ったマスは既に塗られたと確定する。最後に、残っている塗れていないマスを代表ロボでTSPで塗りつぶす。

気持ちとしては、前半を塗ってる内に他のロボが後半を終えていてくれれば嬉しい、ということで後半のマスを多く塗れるようなボタン配置を貪欲に割り当てた。
指示が結構複雑で明確じゃない所も多い気がしたので、プロンプトを5Pにブラッシュアップさせたりして、さらに3つくらい並行してCodexに投げる。

0:57

一番早いのがCodexの作業完了したので提出する。意外と最初のプロンプトでちゃんと組んでくれている。
スコアは333603、そこそこ上位になる。
実行時間は7msでかなり余裕があるので探索範囲を広げてみる。
a.cppを改善せよ。今、下記の方針で設計されているが、最初と最後の1/3の部分をいじって最適化せよ。(以下同上なので省略)
a.cppを改善せよ。今、下記の方針で設計されているが、代表ロボを全パターン試して最善を探すようにせよ。(以下同上なので省略)

1:37

どんどんスコアは上がるがTLEするようになったので高速化を頼む。

a.cppがTLEするので高速化して。差分更新とか、データの持ち方を変えて高速化できないか探って。他にいい方法があればそっちでもいい

事前計算やBFS探索の配列再利用などをしてくれて実行時間が1/10以下になる。

1:40

ローカルでも100ケース回してVisualizerをじっくり見てみる。代表ロボの前半のTSPで他のロボに塗られた所を認識していないので中盤で無駄な移動が発生しているので改善
a.cppを改善して。TSPの前と後ろを塗り終える段階での最善解を出した時点で、解候補のシミュレーションから、ターンAがどこかを計算する。ターンA=TSP前半の方のマスと後ろの方のマスが全て塗り終わった最小のターン。このターンまでを確定して、残りの塗り終わっていないマスを塗っていく、以降の解は同様で。
提出するとスコアは368539。中盤にも関わらず順位表で3位という見たことない位置に上がって焦る。

2:05

最後の塗りつぶしフェイズで代表ロボから塗り残しマスが遠い場合に無駄が多いケースがあったので近いロボに交代
a.cppを改善して。最後に、後ろから50ターンくらいまで見て以下の改善を試す。そのターンが新規マスが塗られたターンでなかったらスキップ。塗られたターンであったら、そのターン以降を代表ロボット以外のロボットで残りのマスを全部塗ることを試してみてターン数が改善するなら最終解候補とする。

2:20

5Pに最新コードを投げて改善案、高速化案を考えさせる
a.cppの高速化をして。BFSをタイムスタンプを使って配列コピーせずに高速かするテクを使って。他にも思いつく高速化を入れて。
a.cppを改善して、今のコードはTSPといいつつ、全然TSPを解いていません。この部分を改善してほしい。ただし、たくさん回すのでいわゆるTSPの焼きなましは時間的に厳しいので他の軽い方法で。
a.cppを改善して。TSP前半後半が終わった時点でのターン数が上位の候補5個に対して、代表ロボ以外のロボを試す順番をランダムに変えたものを何回か試して最善を選ぶようにして。総計算時間は300msくらいだけ割いて。
　

2:40

ここから最後の1時間半は、ひたすらVisualizerを眺めて非効率な所を見つけて改善指示を出す、コードを5Pに投げて改善案/高速化案を出させてCodexに投げる、PRが上がってきたのをスコアとGPTのコメントを参考に選んでマージしていくという流れの繰り返し。
指示は並行で投げているのでレビューする自分がボトルネックになっている。

最終提出になったCodexの作業完了画面

↑最近のCodexは一つの指示に対して最大4バージョンのコード生成をしてくれる。15ケースで簡易テストして前後のスコア変化を計測させるようにしているので、基本的にはスコアが最もよかったものをマージしている。

終了2秒前に投げたこのコードで16位から11位に浮上して過去最高の順位＆パフォーマンスでフィニッシュでした。 焼きなましもビームサーチもなく、ある意味ただの全探索方針でここまで戦えたことに驚きました。