MM166 参加記

私です。

Topcoder Marathon Match 166に参加しました。

前回の AHC069 では、Codexとずっと議論というかアイデア出しをしてもらっていましたが、今回はトークン節約とかそういう関係で、

1. ChatGPTと議論する
2. ChatGPTに実装オーダを作成してもらう
3. Codexに実装してもらう
4. 結果をまとめてもらう

というワークフローで動きました。

結果、マジでいい感じにトークンを使い切れたので作戦成功です。まぁ、コンテストの結果は成功とは言えませんが、他の方々強すぎませんか。やべえよ。私も強くなりてえよ。

問題

今回の問題は、六角形のタイルを回転させて経路を作る問題です。盤面自体も六角形になっていて、一辺のタイル数が $N$ です。各タイルには6つの辺があり、その6辺が2つずつ組になって、合計3本の線が引かれています。タイルは60度ずつ時計回り・反時計回りに回転できます。

盤面の外周には出口があり、

出口0と出口17をつなぐ 出口1と出口42をつなぐ

のように、あらかじめ正しい出口の組が与えられます。タイルの線をたどって、指定された2つの出口がつながれば、その経路は正解です。

また、盤面にはボーナスタイルがあります。ある経路の長さを $L$、その経路が通るボーナスタイルの数を $b$ とすると、その経路の点数は

になります。なので、単に正しい出口同士をつなげればいいわけではなく、できれば長い経路にして、ボーナスタイルもたくさん通したいです。

一方で、最初の盤面からタイルを回転させるたびにコストがかかります。正しく接続できた経路数を $k$、それらの経路の点数の合計を $t$、回転回数を $m$、1回の回転に対するペナルティを $M$ とすると、得点は

です。

正しい経路を増やすこと自体が全体に掛かるので、まず $k$ を増やしたい。でも、経路を増やすために大量に回転すると $mM$ が増える。さらに同じ $k$ なら、長くてボーナスをたくさん通る経路の方が強い。

パッと見た感じは過去改変貪欲とか使う感じなのかな？と思いました。結局、全く使いませんでしたが。

貪欲に経路を作る

出口に $i$ と $i+1$ が指定されているパスを全部完成させて、残ったマスを全部1つのパスにする、みたいな感じで稼げるのではないかと思い、試してみました。

方針としては、

1. まず簡単に完成できるパスを作る
2. 途中で他の正しいパスが完成したら、それも保存する
3. 一度完成したパスはなるべく壊さない
4. 最後に残ったマスを使って長いパスを作る

みたいな感じです。

次にどのタイルを回転させるかも、単純にその瞬間の得点だけを見るのではなく、

1. 行き止まりになる状態が少ない
2. この先到達できる状態が多い
3. 新しく正しいパスが完成する
4. 完成するパスの得点が高い
5. 回転数が少ない

あたりを順番に見て決めていました。

で、これが遅かったので、途中からはアルゴリズムを変えるより先にひたすら高速化をしていました。候補を試すたびに盤面をコピーするのをやめたり、パスの追加判定を $O(L^2)$ から $O(L)$ にしたり、探索に使う配列を使い回したりしました。

途中、小さい盤面だけ厳密に解こうとして、$N=3$ のケースだけを解く最適化ソルバーみたいなものも作ろうとしました。ただ、結局実用化には至らず、提出コードからは消えました。

この辺、最終的に使っていないものにかなり時間を使ったなぁと思います。まぁ、何が効くかを試すのがヒューリスティックだから健全でしょ()

焼きなまし法を試す

貪欲解がまぁ、ある程度できたので、焼きなましに移行しました。

最初は普通にタイルを1枚選んで、向きを変えるだけです。その後、1枚だけだと局所的すぎるだろうということで、隣接する2枚を同時に変更するものも追加しました。

最終的には、

1. 75%で1枚を変更
2. 25%で隣接する2枚を変更

になりました。

この辺から、毎回盤面全体のパスを計算し直すのが当然間に合わないので、変更した場所の周辺だけパスを切ってつなぎ直すようにしました。パスはTreapで持っています。

ここはCodexにかなり頑張ってもらいました。私は横から「もっと速くできるでしょ」とひたすら発破をかけていました。

で、焼きなましを回していると、公式スコアだけを評価値にするのも微妙だなとなりました。例えば、正解が

A - B
C - D

なのに、

A - C
B - D

みたいになっていることが結構あります。

パス自体はちゃんと完成しているのに、出口の相手だけ間違っています。この状態と、そもそもパスが途中で切れている状態を同じように扱いたくなかったので、正しい組かどうかに関係なく、外周から外周まで完成しているパスの長さも評価値に入れました。序盤はこっちもある程度重視して、時間が経つにつれて公式スコアの方へ寄せています。

この辺から、今回の問題って「パスを作る」のが難しいというより、

となってきました。

実際、あるケースでは閉路が1つもなく、全部の出口からちゃんと別の出口へパスが出ているのに、15組中11組しか正しくつながっていない、みたいな盤面ができていました。

線は全部ある。相手が違う。めんどくせぇ〜〜。

ということで、普通にランダムなタイルを変更するだけではなく、正しい相手につながっていない出口を選んで、その出口から伸びているパス上のタイルを変更する方法も入れました。最終的には、変更の30%をこれにしています。

ここもかなり色々試していて、「長いパスなら出口側を重点的に変更した方がいいのでは？」とかもやりました。実際、出口側を変更したときの効率だけを見ると良くなりました。

でも100ケース回すとスコアが下がりました。

よくわかんねえな。ムカ着火ファイア。

ビームサーチも試してみる

焼きなまし解の伸びが飽和してきたので、もしかしてビームなのかと思い、ビームサーチも試してみました。

特に気になっていたのが、さっきの「パスは全部あるけど出口の相手が違う」状態です。1枚や2枚を変更しただけでは、

1. まず1か所を変更する
2. 一時的にスコアが悪化する
3. 別の場所も変更する
4. そこでようやく出口の組み合わせが直る

みたいな変更ができません。

じゃあ、途中でちょっと悪い盤面も何個か残して、その先まで見ればいいじゃん。ということでビームサーチを試しました。

最初は普通に複数の盤面を維持して、そこから候補を作る形です。公式スコアだけで残すと似た盤面ばかりになるので、

1. 公式スコア
2. 正しくつながっているパス数
3. 正しくなくても含めた全パスの状態
4. 出口の組み合わせがどれくらい正解に近いか

みたいな、色々な基準で盤面を残すことも試しました。

ランダムに大きく変更した盤面を混ぜたり、途中で焼きなましを挟んだり、ビームで出てきた候補の周りをさらに探索したり、まぁ色々やりました。

その後、 AHF Vol.1 の資料 を適当に見ていると、ビームサーチと焼きなましの使い分けについての記載があり、「やっぱり今回は焼きなましなのかぁ」となったので、ビーム路線は撤退しました。

結局焼きなましに戻ってくる

ビームサーチも2日ぐらい試してみたのですが、焼きなましの解を越えられなかったので、結局焼きなましに帰ってきました。

ただ、そのまま元に戻したわけではなく、焼きなましが長い間改善しなかったときだけ、それまでの最良盤面へ戻して、普段より少し大きな変更を試すことにしました。

まず、パス上から最大4枚のタイルを選びます。4枚なら向きは

通りなので、ここだけなら全部試せます。

これを1回だけやる方法を試したあと、「1回目は悪化するけど、もう1か所変えたら良くなるやつがあるのでは？」となったので、1回目で候補をいくつか残して、その候補それぞれからもう一度4枚全探索するようにしました。

現在のコードでは幅4、深さ2です。

1回目では、

1. 公式スコアが高いもの
2. 正しくつながったパス数が多いもの
3. 全パス側の評価が高いもの

をそれぞれ残して、最大4盤面に絞ります。

その4盤面からもう一度4枚を選んで全探索して、最後は普通に公式スコアが一番良いものを使います。

なので、最終的には「ビームサーチで盤面全体を探索する」のは諦めて、

普段は焼きなましを高速に回す。詰まったときだけ、少し先までまとめて見る。

みたいな形になりました。

最終的に

この記事を書いているシステムテスト前の段階では、37/74位となっています。もう少し欲しかったなぁ…。

問題自体はめっちゃおもろかったです。単純そうで難しい。こういう最適化の問題を作りたいなぁ…。

今回は途中から、改善案そのものを考えるというより、

1. 何が悪いのかを計測する
2. 仮説を1個立てる
3. 実装する
4. 100ケース回す
5. ダメなら捨てる

みたいなことをずっとやっていました(CodexとGPTにやらせてました)。

周りが強すぎる。マジでこれ。次はもっと上に行きてぇ〜〜。