とりあえず日記だけ。あんまり筋がいい方法じゃない中で頑張った参加記です。
解説は後で頑張って書きます……。
追記：書きました↓
1日目（火）
問題を見た。一瞬直前にやっていたMM139を思い浮かべるものの、その10000倍くらいは難しそう。
何もわからないのでとりあえず貪欲を書く。上下左右に伸ばして得するなら接続＋他の色を中継点にして2方向に伸ばして得するなら接続。とりあえず59.3k点。相変わらず何もわからない。
まあ焼くのかなあ……。とりあえずは愚直に焼こうと思うけど、それすらなかなか難しい。スコア計算はグラフをbitで持てばtzcntで高速化できそうだけど、まずは愚直かな。
そういえばどういうケースを狙うと得かとかあるかな。色数が少ない方がクラスタを大きくしやすい？飛び石を使えないから逆？ちょっと非自明で分からない。スコアは連結成分の大きさの2乗で効いてくるので、ちょっとくらい他の色が入っていたとしても繋げちゃった方が得ではある。1色全部繋げたときの理論値が4950点なので、少なくとも×50ケースで247.5kくらいは出さないとダメだよなあ。MM136みたいに、全体を最適化するよりは選ばれたいくつかを最適化した方が得には見える。
貪欲書いたのはかなり良くて、少なくとも何もない状態よりは圧倒的に考察が捗る。まあ何もわからないのだけれど。
謎クラスカル法とか謎01BFSとかやってみたけどだめだった。寝よう。
2日目（水）
朝には220k点が出ていた。まあさすがにそのくらいは出るよねえ。
焼きなまし方法を考えている。接続はいいとして移動が難しいな。移動の削除を行ったときに整合が取れなくなるケースがある。一度サーバーが置かれたセルは立入禁止にして、絶対に干渉が起きないような移動だけに絞るのが良いか。
辺をフリップするだけの焼きなましを投入。イテレーション数は数百万回。思ったより回るけど、単に連結成分が小さいからかもしれない。提出すると98.1kで48位。さすがに移動も入れなきゃダメだなあ。Kが大きいケースが特に弱い。
3日目（木）
サーバーを移動させる近傍を追加する。かなりバグらせやすそうな気がするので設計には気を使う。案の定バグらせ散らかした。なぜかVS CodeのRustデバッガがon panicでbreakしてくれなくなってしまったのでかなり困る。
どうにかバグを修正して提出すると231.2kで10位。やっぱりちゃんと焼くとそこそこの点数は出る。
接続用コードが通っているマスに移動しようとしたときは弾くようにしていたが、その制約を取り払ってケーブルを繋ぎ直すようにする。あとは温度も調整。259.8kで5位。1位は300kを超えているけれど、ここからどう伸ばすかな……。
いくつかケース見てたけど、seed=7の難易度がエグい。上を目指すならこういうところをどうにかしないといけない……？
あとはひたすらCloud Run上でテストケースぶん回すやつを作っていた。深夜までかけてようやく完成。コンパイルもクラウド上でできるようにするのが地味に大変だった。3秒×1000ケースでざっくり10円か。これなら気軽にポンポンクラウドに投げちゃっても良いな。
4日目（金）
Cloud Run上でテストケースぶん回すやつ、ようやく完成したのでdotnet toolとしてGitHub Packagesにアップロードした。今までローカルで回すだけでも毎回C#プロジェクトをコピペする必要があってかなり面倒だった上、クラウド上で回すには毎回docker buildが必要で本末転倒だったけれど、これからはdotnet tool install <package-name>で入るのでめちゃくちゃ楽。特に短期コンで効果を発揮しそう。いやー満足。
なお肝心のAHC013は1mmも進んでいない模様。気付けば10位まで落ちてる。助けて！
5日目（土）
Cloud Run上でテストケースぶん回すやつ、cold状態から回し始めるのとhotな状態で回すのとでスコアが結構ブレるな。気を付けた方が良いかも。コンテナごとに一発暖機運転を入れると改善するので、ちゃんと比較したい場合はそうするのがよさそう。
ビジュアライザを見ると、ガッツリ動かせばくっつけられそうなのポイントが結構ある。ざっくり焼いた後、大きく移動させることで改善していけないか？
バグらせまくってようやく実装したけど全然スコア上がらなかった。うーん方針外したか。ここで外すのはキツい……。
ABCに出る。Fまでさっさと解けて気持ち良い。Gはベルマンフォードというところまでは分かったが、6乗を5乗に落とせずTLE。解説が賢い。
6日目（日）
今の近傍は小さすぎて局所解にハマりやすいので、もっと大きく動かす近傍が欲しくなってきた。今までの焼きなましのコードも汚いので、思い切ってほぼ全部捨てる。たぶん最終的にはこっちの方が早い。
以下の2つの近傍を実装した。
- あるサーバの接続を全て解除し位置をリセットして、ランダムに移動させて繋げるなら繋ぐ近傍
- あるサーバから乱択BFS（正確には乱択Dial's Algorithm？）を行い、別の連結成分で同じ色のサーバまで繋ぐ近傍
半日かけて実装。さすがにこれだけだとあまり点が伸びない。回数上限をオーバーするような近傍は弾くようにしていたが、これも許容するようにする。ペナルティはオーバーした回数を として、
とした。さらに辺をflipする近傍を追加。ようやくまともな点が出るようになったので提出すると274.2k点。3日ぶりに点数を更新することができた。サーバーの移動も追加すると281.6k。
AGCに出る。2完で温まってよかった。
移動前後にケーブルを繋ぎ直すやつを実装する。295.5kだが、GCPでテストケースを回すとちょこちょこ落ちている。デバッグをいろいろやるが全く原因が掴めない。ちょっとまずいかもしれない。
7日目（月）
今日からお仕事。うーむ有給を取るべきだったか……？
お仕事を早めに切り上げてAHC。移動周りでやらかしているのかと思ったが、BFSでつなぎ直すときにケーブルの自己交差が起こっているのが原因と判明。そりゃダメだわ。修正。
無事落ちなくなったのでパラメータの修正だけして投げ直す。295.5k。よしよし。
雑にいじいじしてたら思いもよらないところで点が伸びた。見てみると後でやろうと実装をサボっていたところと判明。今度はちゃんと実装して投げ直す。320.0k。スコアがどんどん伸びると楽しい。
パラメータチューニングに手を出す。温度と近傍の採用確率をコマンドライン引数で受け取るようにしてoptunaをぶん回す。optunaはローカルで動かし、そこからdotnet tool経由でCloud Runを叩く構成。お金が溶ける音がするが、その分めちゃくちゃ快適ではある。
パラメータの次元数が多すぎるためかお手製の温かみのあるパラメータに負けていたので、温かみのあるパラメータを初期パラメータとして1回trialを回すようにしたところちゃんと人間を超えてくれた。えらい。提出すると331.1k。
辺flipで辺を追加するとき、横切る邪魔な辺を消すようにした。他の近傍では入れていたがこれもサボっていた模様。336.7kで13位。ツカモさんと46点差とかいう接戦になってしまった。
bitsetを普通のbool配列にしたら速くなった。bitsetの方が確保が速いと思っていたけれど、setするときに遅くなって逆効果だったのだろう。
地味高速化をちまちま入れて今日はおしまい。342.8kで9位。やはり高速化は裏切らない……。
8日目（火）
朝起きて業務始めるまでAHC。あちこちでvectorのメモリ確保が起きていたので、vectorを最初に確保して使い回すようにした。予想以上に効果が出て、なんと焼きなましが2倍回るようになった。ここまでで投げると350.1kで10位（上振れっぽいが）。やはりゼロアロケーションは正義……。
optunaを仕込んでおいて、昼休みにパラメータを反映して投げ直す。345.2kで11位。点数は落ちたけど、暫定50ケースより手元の1000ケースを信じる。なんとなく暫定ケースは簡単めなケースが多そうな気がするし。これが最終提出かな。
仕事が終わったら19位まで落ちていてびっくりした。予想以上にみんな伸ばすね……。まあ今更じたばたしてもしょうがない。システスで2ページ目落ちしそうだけど、なんとか残れるようにお祈り。
