THIRDコン2024（AtCoder Heuristic Contest 039）お疲れ様でした。566,997点で優勝しました！久し振りに解説記事を書きます。

問題概要

網を設置してサバをたくさん捕獲してね。イワシを捕獲したら減点だよ。

解法概要

グリッド問題と思い込んで、どのマスを網の中に含めるか焼きなましをします
最初は10x10のグリッドから始めて、20x20 → 40x40 → ... → 320x320と少しずつ細かくします
近傍はグリッドのON/OFF切り替えだけです

ビジュアライザアニメーション。焼きなましをしながら定期的にグリッドサイズを1/2にしている。

AHC039お疲れ様でした！566,997点で多分1位！
幾何ではなくグリッド問題だと思って焼きなましました。最初は10x10のグリッドから始めて、20x20→40x40→……→320×320と少しずつ細かくしていきました。近傍はマスのon/off切り替えだけで、処理がO(1)で終わるようにとかいろいろ頑張りました。 #AHC039 pic.twitter.com/Y9cTcg0bWZ
— TERRY (@terry_u16) 2024年11月10日

この方針にしようとしたお気持ちとしては以下のような感じです。

意外と網の長さ制限が厳しいので、部屋を通路で繋ぐような形式は難しそう
- HTTFの採掘回みたいなやつ
最初は辺をずらす焼きなましを少し考えたが、自分の実装力では4時間だと無理そう
- 幾何をサボってグリッド問題にすれば4時間で実装できそう
グリッドが粗いと細かくサバとイワシを分けるのが難しそう vs グリッドを細かくすると大局的な遷移が難しそう
- 網の長さを縮めるためには行または列全てがOFFになる必要があり、そのような確率はとても低い
- さらに、例えばグリッド1マスの長さが10だった場合、1000離れた位置まで網を伸ばすには100回グリッドのONを繰り返さないといけない
- 最初はグリッドを粗くして、少しずつ細かくしたら両立できるんじゃね？

writer解と同じ方針だったので、AHCラジオもご覧いただくと理解が深まるかもしれません。

www.youtube.com

解法詳細

焼きなまし - 解の持ち方

盤面を $M\times M$ グリッドに分割（初期は $M=10$ ）し、各マスのON/OFFを解として持ちます。初期解は全てON（すなわち $10^5\times10^5$ の正方形）としました。このとき、 $M\times M$ グリッドの外周1マス分を番兵として用意しておくと実装がちょっと楽です。

なお、事前にグリッドの各マスに（サバの数）－（イワシの数）を記録しておくと後述のスコアの差分計算が $O(1)$ で可能です。*1

焼きなまし - 評価関数

特に工夫せず、生スコアそのままとしました。

網の長さを評価関数に入れるということも考えましたが、短期コンでは調整が難しそうなのと、短くすれば良いというものでもないということ（少し離れたところまで伸ばしたいことがある）のとで考慮に入れませんでした。

焼きなまし - 遷移

遷移は各マスのON/OFFのみです。このとき、ONのマス同士・OFFのマス同士の連結性を保ち続けること、網の長さ制限を守ったまま遷移することに注意します。

グリッドの細分化

ある程度の時間焼いたら、グリッドの分割数 $M$ を縦横2倍にします。図を見るのが分かりやすいかなと思います。

処理の雰囲気は擬似コードで書くとこんな感じです。実装はそこまで重くないです。*2

# サバとイワシの座標の読み込み
n = int(input())
saba_points = read_points(n)
iwashi_points = read_points(n)

# グリッドの分割数（初期は10x10）
m = 10

# 初期解として全てONである10x10グリッドを生成
on_off_grid = make_initial_grid(m)

while m <= 320:
    # グリッドの各マスにおける（サバの数）－（イワシの数）を計算
    saba_iwashi_grid = calc_saba_iwashi_grid(m, saba_points, iwashi_points)

    # 前回のグリッドの状態を初期解として焼きなまし
    on_off_grid = simulated_annealing(saba_iwashi_grid, on_off_grid)

    # グリッドを縦横半分に分割
    m *= 2
    on_off_grid = split_grid_half(on_off_grid)

多角形の復元

グリッドの外周の適当なマスから始めて、左手法で壁を伝っていくことで解を復元します。結構実装が面倒なので頑張ります。*3

なお、 $M$ を大きくすると意外と多角形の $1000$ 頂点制限がキツくなってくるので、一直線に並んでいる頂点はちゃんと始点と終点以外を消すなどの工夫が必要となります。*4

高速化

グリッドを細かくしていくと処理速度が欲しくなってくるので、高速化を頑張ります。最終的にはジャッジサーバー上で $10^7$ 回ほど焼きなましが回るようになりました。

連結性判定

遷移を行ったときの連結性判定はDFSをしたりlowlinkを使った関節点検出をしたりといった方法でも可能ですが、これには $\Theta(M^2)$ かかってしまいます。

そこで、OFFにしようとしているマスの周囲3x3マスのみを見ることで、 $O(1)$ で簡易的に判定するテクを使います。3x3マスより外側で繋がっている可能性もあるので厳密な判定ではありませんが、安全側の判定となるためこれによって連結性が壊れることはありません。*5

Shun_PIさんのスライドも参考にしてください（資料内p.18）。

www.docswell.com

なお、今回は多角形が自己交差してはいけないという制約が存在するため、OFFにしてよいかという判定だけでは上手くいきません。といっても難しいことをする必要はなく、マスをONにしようとするときはOFFとなっているマスの連結性が崩れないかをチェックしてあげればOKです。

網の周上に隣接するマス集合を管理

マスのON/OFFを行うとき、網の周上に隣接するマス以外を対象にしてしまうと必ず非連結となってしまい、有効な遷移となりません（下図参照）。有効な遷移となるまでマスをランダムに選び続けてもよいですが、そのようなマスを引く確率はざっくり $1/M$ のオーダーなので、分割数を細かくすればするほど無駄な乱数生成が増えてしまいます。

そこで、網の周上に隣接するマスの集合を管理して、その中からランダムに選ぶようにしました。これも頑張れば差分更新が可能です。集合の管理にはtomerunさんの[0,n)の整数の集合を管理する定数倍が軽いデータ構造を使いました。

コンテスト中の立ち回り

どういう動きをしていたかざっくり時系列で書き並べてみます。

準備（～0h00m）

AHC開始前に準備をしておきます。といってもAHCテンプレを準備したりするわけではなく、おやつを買ってコーヒーを淹れただけです。*6

問題の理解と諸々の準備（～0h31m）

問題文を読み、幾何問題っぽい雰囲気にウッとなります。とりあえず出力例のビジュアライザも眺めて、複雑な多角形が出力されていることを確認してこの実装はキツそうだなあという気持ちになりました。

第一感としてパッと思い浮かんだのはHTTF2021本戦でしたが、複雑な図形同士を上手く繋げられる気がしませんでした。

とりあえずローカルでの並列実行環境の整備と入力の読み込みまで実装し、 $10^5\times 10^5$ の正方形を作る自明解を出しました。自明解がちょうど網の長さ制限ピッタリで意外と周長制限がキツいことに気付いたので、とりあえず自明解を提出するというのは良いかもしれません。

方針決定と焼きなまし実装（～1h37m）

幾何がキツくて4hで実装できる気がしないので、幾何を避けたい
周長制限がキツいので、貪欲・ビムサ系よりは全体を見て良い感じにする焼きなましの方を適用したい

という方向性で考えていたところ、開始40分時点くらいで「グリッドにすれば両方解決するのでは？」とアイデアが降ってきました。また同時に「最初はラフに焼いて次第に細かくすればよいのでは？」というアイデアも思い付きます。短期コンならこれを実装すればさすがに1ページ目には行けそうな手応えを感じたので、実装に移ります。*7

とりあえず10x10のグリッドで実装してみました。3x3領域だけ見て連結性を判定するテクもここで入れています。細かいところで結構バグらせてしまったので、グリッドの状態をコンソールに吐きながら丁寧にバグを潰していきます。

seed=0で試してみると2300点くらい出ていて、このときの順位表1ページ目が300k～400kくらいだったので、10x10の粗いグリッドでこの点数だったらかなり行けるのではないかという気持ちになりました。

なお、焼きなましのスコアとしてはこのくらい出ていますが、多角形の復元を実装していないため提出はまだできない状態です。この2300という数字が焼きなましくんの妄想でないことを祈ります。

バグ修正（～1h49m）

近傍の選択確率をミスっていてマスのOFFしか行われていなかったので直しました。あの……。

修正するとseed=0で2800点くらいになりました。かなり良さそうです。

多角形の復元を実装（～2h24m）

焼きなましで良いスコアが出そうなのは分かりましたが、求められる出力形式に直さなければ0点です。泣きながら実装します。

提出すると441,935点で11位でした。予想通り良い順位が出て嬉しくなります。

グリッドの微細化を実装（～2h38m）

10x10グリッドでこの点数なので、微細化を入れればかなり良くなりそうです。というわけで実装します。グリッドサイズはどのくらいが良いかよく分からないので、とりあえず10x10開始で80x80まで微細化することにしてみます。

こちらの実装はシンプルなのですぐ終わりました。提出すると551,282点で1位になりました。嬉しくて調子に乗っています。

お世話になっております。 pic.twitter.com/xP0lPCPDPU
— TERRY (@terry_u16) 2024年11月10日

周上のマス集合を管理（～3h20m）

実行時間を伸ばすとほんのりスコアが改善しそうな雰囲気があったので、高速化に着手します。グリッドが粗いうちはそこまでネックにならない気もしますが、今後グリッドをさらに微細化していくことも考えるとやはり速い方が有利そうです。

こちらもバグらせながら実装すると、それなりに有効な近傍遷移数が増えました。とはいえ点数はそこまで大きくは伸びず、552,871点でした。

さらにグリッドを微細化（～3h38m）

ビジュアライザを見るとまだグリッドが粗いように感じたので、思い切って320x320まで分割するようにしました。すると多角形が1000頂点制限に引っかかるようになったので、一直線に並ぶ無駄な頂点を削除する処理も入れてあげます。

提出するとかなり伸びて、565,986点になりました。2位のchokdaiさんも556k点に伸ばしてきていたので、ここで10k点以上伸ばせたのは大きいです。

パラメータ調整（～4h00m）

やりたいことはやり尽くしたので、最後はパラメータ調整をします。最終的に566,997点になりました。

パラメータや乱数のブレの範囲ではなく余裕を持って1位が取れたのでとても嬉しいです。

感想

パッとしない成績が半年続いていたのでそろそろ勝ちたいと思ってはいたのですが、年内に2回目の優勝ができるとは思っていなかったので自分でも驚いています。GP30もwriter補正込みで既に418.8点となっていて、今期は大成功と言って良いですね。

一見不可能幾何問題っぽく見えましたが、グリッド問題に落とせるということ、グリッドを少しずつ細かくすると大局的にも局所的にも良い解が出せるということがとても面白い問題でした。方針を思い付いたときにこれは行けるだろうと感じたのですが、その後実際にかなり良いスコアが出せたのも久々に勘を取り戻せた感があって良かったです。writerのwataさんとほぼ同じ方針だったというのも嬉しいですね。

前回の優勝もTHIRDコンだったので、THIRDさんは毎月AHCを開いてください！どうもありがとうございました！

*1:ちなみにこの方法だと網の境界上に乗っている魚が片方のグリッドにしか含まれないという問題があるのですが、スコアにほとんど影響がないのと修正が激しくめんどくさそうなのとでで無視しています。

*2:むしろ後述の多角形の復元の方が大変……。

*3:私はバグらせまくって実装に30分かかりました……。

*4:M≦250であればグリッドの1辺の長さが400以下であるため、周長400,000以下という制限を守れば1000頂点を超えることはありません。M>250の場合は1000頂点制限に引っかかる可能性があるため注意が必要です。

*5:私は全パターンの連結性をコンパイル時に前計算しましたが、AHCラジオによると消去可能性を四則演算で判定する方法があるらしいです。

*6:ローカル並列実行環境の整備に5分くらいかかるので、予め準備しておきましょう……。

*7:今回は上手く行きましたが、手応えがあっても全然スコアが伸びないということもあります……。

TERRYのブログ

最近は競技プログラミングにお熱。

THIRD プログラミングコンテスト2024 (AHC039) 解説