AHC066で15位になりました。
自分のメモもかねて解法を記事にしました。
提出コード：Submission #76524677 - AtCoder Heuristic Contest 066
解法
マクロは原則1つで固定し、固定するマクロを探索しました。
おおまかな解法は、マクロ探索→ボール回収順改善の山登り→後処理 です。
マクロの探索
まずseed0000~3000を解き、使用したマクロを埋め込んでおきます。
埋め込むマクロはNとT/2MN^2<=0.2かどうかで分類し、入力に合うものを初期のマクロ候補とします。
マクロの評価は後述のビームサーチによっておこないます。
埋め込んだマクロだけではいまいちなので、評価済みマクロのうち評価値が高いものに対して変更を加えて新たなマクロ候補を作っていきます。
新たなマクロ候補を作る際に加える変更は以下の通りです。
- F/FFをL/Rの前後に挿入
- L/Rの挿入
- 1文字変更
- 1文字削除
変更を加えた結果、LRやRL、LLL、RRRがマクロ中に発生する場合はその変更を棄却しています。
また、マクロのすべての文字に対して1文字変更/削除をすると候補数が多くなるので、これらの変更は1つのマクロに対して最大3回ずつに制限しています。
評価済みマクロの集合から評価値で重みづけしてマクロを取り出し、取り出したマクロに上記の変更のうち1つを加え新たなマクロ候補とすることを繰り返します。
マクロの評価順序は、埋め込みマクロと変更を加えたマクロを交互に評価するようにしています。
埋め込んだマクロ候補が最終的な解に採用されている割合は20%程度だったので、変更を加えるのが結構効いているようでした。
マクロの評価のビームサーチ
マクロの評価は、マクロを固定したときの操作列をビームサーチで求めたものを用います。
ビームサーチは1つのボールを取ってかごに入れるのを1手とします。
1つのマクロの評価にあまり時間を取らないようにビーム幅は30にしています。
ボールを取ってかごに入れる経路はBFSで求めたマクロの使用を含む最短経路を使っています。
評価関数は「ここまでの操作列長 + 未回収のボール→かごの最短経路の和+ 展開長のペナルティ」としています。
展開長のペナルティは (展開長)/T > 0.85 の場合のみ、展開長に応じて最大15のペナルティを与えています。
M<=7のときはbitDPでも高速に動くのでビームサーチではなくDPを使っています。
ビームサーチは状態をコピーする素朴な実装にしています。
状態が50バイトくらいで軽いので差分更新にしても変わらないと思い差分更新にはしませんでした。
NextBeam（評価済みノードを入れとくやつ）はビーム幅の二倍のサイズになるたびにソート+resizeしています。
また、NextBeam内の（ソートされたノードの）最も悪い評価値より良い評価が見込めない親ノードからの遷移は枝刈りしています*1。
ビームサーチで操作列を求めたあとにマクロ定義部分のみの後処理をおこなっています。
例えばLFFFFFLFFFFFLFFFFFのようなマクロは、MFFFFFMMLPLPLPMとすることで定義部分を圧縮できます。
このような後処理をおこなった後の操作列の長さをマクロの評価値としています。
山登りパート
上記のマクロ候補生成と評価を1800~1880ms程度おこなったあと、評価が高いいくつかのマクロに対して山登り法でボールの回収順の改善をおこないます。
ビームサーチをしたときの回収順を初期解として、swap,insert,2-optなどの近傍で山登りをします。
回収順を固定したときの操作列長はDPで出せるのでそれを評価関数にしています。
全く改善しないケースもありますが、平均で3~5手程度改善している気がします。
山登りの結果最も操作列が最も短くなったものを最終的な解とします。
後処理パート
最終的な解に対して後処理をおこないさらに短縮します。
ビームサーチの後にもおこなっていたものに加えて、以下の2点をおこなっています。
- 操作列の終わりが...PPSLPPSRPPSみたいな場合はMPPSMLPRPとマクロを再定義することで短縮できるので、操作列を後ろから見ていきマクロを再定義することで短縮できればそうする
- マクロ再生中に壁に当たったりする関係で、操作列から1,2つ操作を削除してもすべてのボールを回収できる場合があるので、そのように削除できる操作があれば削除する
やらなかったこと
マクロ探索の焼きなましは、探索空間をなだらかにできずすぐ局所解にはまる気がしたのでやりませんでした。
壁に当たったらその場にとどまるため、マクロを少し変えるだけで壁に当たるタイミングが変わり、経路が大きく変わる可能性があるので探索空間がガタガタになりそうだと判断しました。
埋め込みの数を増やしたり、使う埋め込みをM基準にしたりしましたが、スコアが下がったのでやめました。
順序探索の山登りを焼きなましにしてみましたがこれもスコアが下がりました。
AIについて
内容によって以下のようにモデルを使い分けていました。
- 解法の実装：codexからchatGPT5.5-medium/high
- データの集計やちょっとした実験スクリプトの作成など：Gemini Flash 3.5（antigravity CLI経由）
- 考察の壁打ち、高速化アイデアの提案、解法の改善案の提案：chatGPTのチャットとcodexからchatGPT5.5-xhigh
解法の実装以外にcodexを使わないことで、chatGPTのplusプランでもcodexの使用量制限に余裕をもってコンテスト期間を過ごすことができました。
AIに渡す問題文はh,ul,li以外の不要なhtmlタグを除去しています。
基本的に解法は自分で考えて、実装をAIに投げるスタイルでやりました。
AIに改善案を考えさせてもいまいちなものしか考えてくれないので、自分の考察がつきたときに参考程度に考えさせていました。
高速化もAIにやらせるとデータ構造系の高速化しかやってくれず、問題や解法の特性を活かした枝刈りなど本質的なものは提案してくれないので、その辺は自分で考える必要がありました。
感想
これ系の問題は苦手意識があったのですが、短期含めて最高順位が取れてうれしいです。
かなりがんばったのでやり切った感はありますが、ビムサの評価関数や埋め込み候補数、ビムサと山登りの時間配分などはちゃんと調整したほうがよかったなというのが反省点です。
上位の解法を見ているとまだまだ自分ではたどりつけないものが多いので、いろんな解法を読んで勉強していきたいです。
個人的にはM挿入の過去改変ビームサーチが賢いなと思いました。
入力別の順位を見ると壁なしのケースで順位が低くなっていました。
ここまで顕著に差がつく心当たりがないのでよくわからないです。
最近は貪欲やビームサーチが強い問題が多いので、そろそろ焼きなまし高速化バトルがきてほしいです。
次の長期はあまり取り組む時間をとれなさそうなので、まずは6月7月の短期をがんばりつつ、今年中の銅冠を目指して引き続きがんばっていきます。
*1:これなんかで見た気がするんですが、汎用的なテクなんですかね
