AHC041 41位解法 | ardririyの足跡

新年初AHCは75,269,940点で41位と、今までで最も良い成績を取ることができました！大変嬉しいです。それを記念して解法を書きます。
ビジュアライザ Seed=0,Score = 502906(色はscoreを表示)

Christmas Tree Cutting

クリスマスのためにグラフから見栄えの良い木を切り出してね。( 問題へのリンク )

解法

解法は初期解生成から、頂点を一つ乱択して親となる頂点を変更するシンプルな焼きなましです。最終提出

初期解生成

初期解生成は制限付きのBFS を、 \(A_i\) が小さい順に行う方針で行いました。根に近い頂点が多いと得点的に勿体ないので、「深さが \(d\) の頂点から伸ばせる辺の数は \(\max(\lfloor \frac{d}{2} \rfloor, 1)\) 」という制限を掛けることでできるだけ深い位置にある頂点を増やすこと狙っています。また、伴って根に近い頂点はできるだけ見栄えが悪い頂点であってほしいので、 \(A_i\) の値で昇順にソートして訪問する頂点を決めています。
この時点でのビジュアライザはこんな感じ。全体的に悪くは無いですが、切り株のような木がいくつか存在することが気になります。(seed=0,Score = 434105 表示モードは高さ)

焼きなまし(遷移)

焼きなましは頂点を一つ乱択し、その後その頂点から出る辺を一つ乱択して付け替え先の親の候補を選びます。
もし遷移したときに制約違反(高さが10を超える)が発生する場合は遷移をrejectします。点数は公式ツールを参考に、毎回全体を再計算します。

本当はDFSを書いているつもりで、しかもあとからよく見るとChatGPTにも指摘されていたが、終わるまで気づいていなかった。あの？

こういうところはRustを使う利点

Seed=0, Score=472369, 表示モードは高さ

なお、この時点での焼きなましは全然回っておらず、確かジャッジ環境で10万回ぐらいだったはずです。「点数が悪化する場合はその悪化度合いに応じて確率で遷移」としており、時間に寄る確率が入っていません。

焼きなまし(高速化)

全然回っていないということで、高速化する必要があります。全体を再計算すると重いですが、よく見ると点数が変わるのは親を変更した頂点以下の部分木のみですから、この部分だけを見るようにすればよいです。親→子への有向辺があると思ってグラフを構築し、また別途高さを管理しておくことで、更新時のスコア差分は親を変更した頂点を根とする部分木の大きさを \(M\) とすると \(O(M)\) 時間で計算が可能になります。

実はこの差分計算はうまくやると定数時間でできるらしいですが、そんなことには気づきません

これはそこまで大変な変更ではなく、実装をするとジャッジ環境で800万回程度回るようになります。この変更を加えたと同時に、十分な回数が回るようになったので時間経過に寄る遷移確率の変更を取り入れます(線形に減少するようにしました)。
最終提出: seed=0, Score=502906, 表示モードは高さ

コンテスト時の動き

問題を読む・1, 2回目の提出 (~30m)

問題を読みます。クリスマスツリーだから木を構築するのかｗとちょっと楽しくなります。
問題を誤読します(え？)。根に近いほうが上に来ると思っていたのでDFSで見栄えの悪い頂点を使って一パス掘って、あとはBFSで２段分掘って傘のようにしたものを提出します。
提出してビジュアライザを見ると明らかに点数が出ておらず、誤読に気づきます。DFSを解つもりでBFSを書いていますが、うまく制限を掛けたことでそれなりに点数が出てしまい気づきません。提出すると66053303点でした。序盤ということもあり提出も少なく、悪くない順位につけます。
この提出時点でpahcerがこんな感じ。

Average Score          : 439,096
Average Score (log10)  : 5.642
Average Relative Score : 100.000
Accepted               : 100 / 100
Max Execution Time     : 8 ms

実際には提出する直前に誤読に気づいていたが、まぁいいやで出した

この辺もDFSをしていないことに気づいていない原因

山登りを書く(~1h)

困りました。BFS解を書いて万策尽きてしまった。
仕方がないので、気持ち程度に適当な山登りを書くことにします。近傍は...あ、親を付け替えるのが簡単そうかな？実装も重くなさそうです。
点数計算を書いて、遷移を(ほとんどcopilot丸投げで)書いて、実行すると意外と改善していそう。

Average Score          : 457,238
Average Score (log10)  : 5.660
Average Relative Score : 104.133
Accepted               : 100 / 100
Max Execution Time     : 1,997 ms

100ケース平均で1万点ぐらい上がっています。ということは150万点ぐらい伸びそう？と思いながら投げると、68756840点でした。いい感じです。

今コンテスト終われ！ pic.twitter.com/WbVsk4uhIF
— りり❄* (@ardririy) January 19, 2025

焼きなます(~1h40m)

AtCoder環境でaccept数を見てみると、なんと200回もacceptされていると驚きます。あまり回数回っていないのが気がかりですが、Writerのterry-u16さんも「山登りができるということは焼きなましができる」といっています。ということで、焼きなましにしましょう。
え、温度を線形に下げると死ぬほど性能が出ません。山登りしたほうがマシです。うーんと思いながら温度の概念を消すとなんと点数が上がって驚きます。

Average Score          : 475,057
Average Score (log10)  : 5.677
Average Relative Score : 100.468
Accepted               : 100 / 100
Max Execution Time     : 1,998 ms

焼きなまし(？)という感じですが、まぁ点数が上がったので投げます( 提出 )。なんと大台の71Mに乗ります。

高速化する(~2h40m)

回数が回っていない原因が毎回得点の全体再計算していること、またそれを改善する方法も頭に合ったので、それを実装します。珍しくバグらせません。日頃のアルゴ精進のおかげです。
pahcerを回すと、かなり改善しているのが見て取れます。

Average Score          : 498,561
Average Score (log10)  : 5.698
Average Relative Score : 103.751
Accepted               : 100 / 100
Max Execution Time     : 2,000 ms

提出します75M弱の点数が出て、びっくりするとともに「久々に勝てるぞ...！」と心が震えます。

今AHC終われ！！！！！！！！！！！！！！！ pic.twitter.com/x74juuo3vj
— りり❄* (@ardririy) January 19, 2025

風呂に入る・ご飯を食べる(~3h50m)

マジで何も思いつかないので風呂に入ってご飯を食べました。

パラメータ調整をする(~4h)

そういえばパラメータ適当にいじったままだな～と思いながら適当に弄りながらpacherに投げて、良くなったものを提出しました。その甲斐あって、なんと75Mに乗って大勝利を確定できました！

お疲れ様でした～～～～初2桁順位だ！#AHC041
— りり❄* (@ardririy) January 19, 2025

この時点では本当に大した効果が出ると思っておらず、ちょっとでも点が伸びたら嬉しいなぁぐらいの気持ちで書き始めている

これを言っていたGitHub Pagesの日記を過去に読んだのだが、URLを紛失してしまい見つけられなかった

感想

まさかこんないい成績を出せるとは思ってもおらず、また今年のヒューリスティックの目標は2桁順位を取ることだったので、新年早々達成できてメチャクチャ嬉しいです。やったね✌