AHC041の復習

AHC041（ALGO ARTIS プログラミングコンテスト2025 冬）の復習を今回はかなり気合入れてやってみたので、自分用の備忘録としてまとめてみる。ちなみに本番の自分自身の順位は344位で大惨敗でした。

問題

問題について詳細はリンクを参照。要約は以下の通り。

$N$ 頂点 $M$ 辺の連結単純無向グラフ $G$ があり、各頂点 $u$ には数 $A_u$ が書かれている。 $G$ の部分グラフで最大高さ $H$ 以下の根付き木からなる森について、その森のスコアは各頂点 $u$ の高さを $h_u$ としたとき $1 + \sum_{u = 1}^{N} (h_u + 1) A_u$ となる。スコアを極力大きくするような最大高さ $H$ 以下の森を出力せよ。

制約

$N = 1000, ~ 1000 \le M \le 3000, ~ H = 10, ~ 1 \le A_u \le 100$.

解法

Writerのスライド、コンテスト後のX、優勝者のブログ、上位者の提出コードなどを参考に書いてみた解法をまとめていく。 Xに投稿したツリーはこちら。

AHC041復習ツリー🌲
— みーとみ (@miiitomi) January 20, 2025

自明解：954位相当

全頂点を根にする。
提出

BFS：741位相当

適当に根を決め、そこから距離 $H$ までで到達できる点までBFSで辿っていく。
提出

DFS：455位相当

同じことをDFSでやる。
提出

昇順DFS：259位相当

DFSで、辿る頂点は $A_u$ の値が小さい方を優先的に探索する。
提出

昇順DFS + 根全探索：146位相当

基本は昇順DFS。新しく根を選ぶときは、まだ未到達の頂点を根とした場合をすべて試し、新しい木のスコア/頂点数が大きくなるものを選ぶ。
提出

昇順DFS + 根の順番焼きなまし：65位相当

基本は昇順DFSで、新しく根を選ぶときはあらかじめ決められた優先順位でもっとも早いものを根とする。
その優先順位を焼きなましする。近傍は優先順位リスト内の二点スワップ。
提出

高さ焼きなまし：42位相当

高さ配列 $h_u$ を状態として持って焼きなましをする。
- 頂点 $u$ を一つランダムにとり、$u$ の親候補 $p$ を $u$ の隣接点と $-1$ ( $u$ 自身を根にする) から一つランダムに選ぶ。
- $u$ の高さを $h_p + 1$ とする近傍を考える。
  - その遷移が可能かは、頂点 $u$ の全隣接点に適切な親候補がいるかを確認すれば良い。
提出

高さ焼きなまし + 温度調整・高速化：7位相当

温度パラメータの調整
- 初期温度200、最終温度0.1として線形に温度を落としていく。
高速化
- 焼きなましループ内で毎回時間計測してると遅いので、ループ1万回に1回時間計測にする。
提出

部分木付け替え焼きなまし：12位相当

部分木付け替え焼きなまし
- 頂点 $u$ を1つをランダムにとり、$u$ を親とする部分木を丸ごと別の隣接点に付け替える（ $u$ の親だけ変える）/$u$自身を根にする近傍を考える。
- $u$ の子孫で高さが $H$ を超えることがなければ遷移可能。
- 詳細はWriterの解説スライド参照。
提出

部分木付け替え焼きなまし + 高さ違反許容：4位相当

序盤は最大高さが $H$ を超えるのを許容する（30程度まで）。
高さ違反のペナルティを時間経過に伴って指数的に増やしていく。
- 詳細は同じくWriterの解説スライド参照。
あとこちらでは焼きなまし温度も指数的に変化させるように変更。
提出

高さ違反許容部分木焼きなましの高速化：3位相当

高速化：擬似乱数生成をメルセンヌツイスタ（mt19937_64）ではなくXorshiftを使う。
提出

高さ $h$ の小さい方から最小限の頂点を高さ $h$ にしていく貪欲：15位相当

高さ $h$ の小さい方から最小限の頂点を高さ $h$ にしていく。
- ある頂点 $u$ を新たに高さ $h$ にしたとき、高さ $H$ 以下となりうる未達頂点の集合を $T_u$ とする。
- $T_u$ のunionが未達頂点全ての集合に一致するように、最小限の頂点を高さ $h$ にする。
詳細は優勝者のブログ参照。
提出

ビームサーチ：2位相当

各高さ $h$ ごとに、高さリストを状態として持つビームサーチ。
- 各高さを決める時の貪欲法において、$A_u$ に適当に乱数を加算することで複数遷移を作る。
- 詳細は同じく優勝者のブログ参照。
提出

ビームサーチ2：1位相当

同じくビームサーチ
- 上の遷移に加え、高さ $h$ とする頂点を選んだ時に、ある点を別の頂点と変更するスワップによる遷移も追加。
- 詳細は同じく優勝者のブログ参照。
乱数探索回数やビーム幅を適当に調整して本番1位相当に。
提出

上のビームサーチに新しく高さをhにする頂点の変更をする遷移を追加して、諸々調整したら本番1位相当出た！76952094点（本番1位相当）！
くぅ～疲れましたw これにてAHC041復習完結です！！https://t.co/wU64sAs1IX pic.twitter.com/TRS70F8XMd
— みーとみ (@miiitomi) January 27, 2025

まとめ

Writer、上位入賞者、優勝者の解説を理解した上で提出コードも読み込んだらすごい勉強になった。今後もAHCごとにこんな感じで復習続けていって強くなりたい。