📚

AHC060　参加レポ【1位 スコア175k】

に公開
競技プログラミング
ahc
tech

はじめに

AHC060で1位を取れました。さすがに記念ということで参加レポと簡単な解法記録を残しておきます。
あくまで参加レポのつもりで書くので肩ひじ張らず読んでもらえると幸いです


さすがにラビー

問題文

問題文は以下のリンクから

https://atcoder.jp/contests/ahc060/tasks/ahc060_a

滅茶苦茶ざっくり要約すると。

  • アイスのノードが90個とお店のノード10個の連結グラフがあり。このグラフを動き回ってコーンにアイスを積んでいってお店に納品する。
  • 積んだアイスはWとR二つの文字の文字列で表現されて、アイスのノードにたどり着くとWかRのどちらかが文字列に積まれる。
  • 初期状態ではどのアイスのノードもWを文字列に積むが、プレイヤーは現在地のアイスノードのフレーバーをイチゴに切り替えることで次回以降のそのノードで積む文字をRに切り替えれる。ただし逆はできない
  • お店のノードにたどり着くと手持ちの文字列を納品できる。ただし同一店舗で以前全く同じ文字列を納品していた場合、手持ちのアイスはなくなるが納品数は増えない。
  • 全店舗での納品数の合計を最大化しよう

といった感じ

解法

基本方針

基本的な方針はtwitterにも書きましたが

  • 各ノードにkターン目以降に訪問したタイミングでイチゴ味にするというパラメータを持たせ、パラメータの値を焼きなまし
  • シミュレーションはBFSベースで、在庫が重複するような経路は棄却しつつ貪欲に短い経路を探す

といった感じです。
似たような方針で解かれてる方は結構見受けられましたし、私自身も本番中「なんで普通の発想の回答でこんな順位表高いのか」と思ってました。
なのでぶっちゃけ何がそんなに上手くワークして高得点になったのかは現時点でもあんまわかっていません。
Q.じゃあ運勝ちじゃねぇか
A.そうです...（真久間メガ)

とはいえここら辺が上手くワークしたんじゃないかという推測はあるのでそちらを紹介していきます。

シミュレーション部分について

おそらく最も有効に働いていたのはこのシミュレーション部分の工夫です。
というのもこの問題、真正面からBFSを適用しようとしてもあまり上手くいきません。
この問題では納品文字列の多様性を担保する観点から、少し遠回りしたりサイクルでループしたりといったパスを考える必要があるわけですが普通のBFSではvisitedを管理する関係からそういったルートは考慮できないんですね。
なので今回私のシミュレーションではBFSでvisitedを管理しませんでした。

「そんなことしたら組合せ爆発起きてまともにシミュレーションが動かねえだろ」と思われると思いますが。

  • 生成されるグラフが、ドロネー分割からさらに辺を枝刈りしたものになっている関係でノードの次数が控えめなうえ、ルール上Uターンが禁止されているのでルートの分岐が控えめ。
  • ゴールである店のノードが全体の1割を占めるうえ、納品は一文字でもずれてたらOKのためWとRが適度に混ざっている盤面では比較的すぐにルートが見つかる。
  • 特に指示してないのに、ある一定以上で探索を打ち切って一旦近くの店舗に移動して探索をやり直す処理をClaudeが書いてくれたおかげでコーナーケースでもスタックせずに済んだ

など様々な条件が重なった結果、なんか動いてくれました。

ちなみに本番中にこの処理作っていた時は特に上記のような考察をしていたわけではなく、「visited管理しないと組合せ爆発がする」というBFSの基本を普通に忘れていました。
Q.やっぱ運勝ちじゃねぇか
A.そうです...（メガ・マグマ・ドラゴン)

このシミュレーションが何故かやたら強く

  • とりあえずアイスノードに到達するたびに1%の確率でフレーバーを切り替える設定でシミュレーションを回すだけで156k(本番112位相当)
  • フレーバーを切り替える確率をグリッドサーチで時間いっぱい試すと162k(本番59位相当)
  • 特に工夫を加えず、上記基本方針の山登り版を行うと172k(本番4位相当)

といった具合でした。

ビジュアライザを眺めての感想としては、このシミュレーションはサイクルを使うのがかなり上手いように見えます。
seed0だと店舗0や4の周辺が顕著ですが、グラフ生成にドロネー分割が使われている関係で辺数の少ないサイクルが入り混じった構造が多く、そういった構造で上手いことループを回して納品数を稼いでいるようでした。


ここら辺のこと


こちらはseed12 こんな感じでずっと同じところを周回しながら在庫を稼いでいる

他の方の回答では事前にパスを列挙して置き、その中から貪欲にパスを選ぶという発想の方が結構見受けられましたが、その方針との差別化点はおそらくこのサイクル部分の処理の仕方にあるように感じます

その他工夫

上記のようにシミュレーション部分でかなり重い処理をしているため、上記の山登り解では、seedによってイテレーションが400回程度で終わってしまっていました。なので

  • とりあえずClaudeとGPT5に案出ししてもらい諸々高速化
  • 近傍を1ノード分のパラメータ変更だけにして前回シミュレーション時との差分を少なくし、シミュレーションを差分が出たターン以降だけにする

みたいな工夫を加えて何とか最低でも1500回ぐらいは回るようにして、最後に山登りを焼きなましにすると175kが出ました。
ちなみに最後の最後に300点ほど巻き返したのはパラメータの初期解をすべて[0,10000]から一様乱数で選んでいたのを[500,9500]から選ぶように変えた部分でした。
これは最初の方と最後の方は1色に染まっている時間があった方がいいのではないかという直感からの発想でしたが、別に確たる理屈があったわけではないです。
Q.結局最後の最後まで運じゃねぇか
A.そうです...（勝利宣言 鬼丸「覇」 キャラプレミアムトレジャー)

完走した感想

こうやって振り返ると徹頭徹尾、運とAIのパワーだけで上手くいっている感が否めません。
twitterの方でも書きましたが、短期AHCはゲーム性を大きく毀損しているという理由でAI禁止されてももう文句は言えないかなと思います。

ただ一方でAI禁止されたら勝てなくなるというポジショントークを抜きにしても、やっぱりAIは禁止してほしくないなと思っています。というのも私みたいな競プロは興味あるけど個人開発とかはしてないみたいな層にとって、AHCは手軽にプライベートでバイブコーディングの勉強ができるいい機会だと思っているからです。
実際、今回のAHCは初めてClaudeを自環境に導入して挑戦したAHCだったのですが、コンテキストの無駄遣い等々、AIエージェントの使い方について建設的な学びが得られました。AHCみたいに限られた時間リソースで課題を与えられる場でAIを使わないと、こういう知見は育ちにくいんじゃないかと思っています。
まあそもそも、AHCはバイブコーディングの練習場ではないしそういうのは別途各自やってくれといわれたら、ぐうの音も出ませんが...

Discussion