AHC041解説

AtCoder Heuristic Contest 041（ https://atcoder.jp/contests/ahc041 ）の解説放送で使用した解説スライドです。

Transcript

1. AHC041 解説 2025/1/19 writer : terry_u16
2. 簡単な考察： どのような木が望ましいか 高い場所にあるほどスコアにかかる倍率が上がる できるだけ高い場所にたくさん頂点があるような木を作りたい ℎ = 0 ℎ = 1 ℎ = 2 ℎ = 3 低スコア 高スコア
3. 解法例1 : DFSベース解法
4. ① とりあえずACする 全ての頂点を根（-1）とする 7,584,268点 （本番954位相当）
5. ② BFS木を作る まだ使われていない頂点を根として、BFS木を作る貪欲 55,988,632点 （本番741位相当） BFS中、頂点𝑢から頂点𝑣に 移動するときに辺を張ると 木ができる
6. ③ DFS木を作る まだ使われていない頂点を根として、DFS木を作る貪欲 67,252,287点 （本番455位相当） DFS中、頂点𝑢から頂点𝑣に 移動するときに辺を張ると 木ができる
7. BFS木とDFS木 BFS木よりDFS木の方がスコアが高い BFSは近い頂点から順に訪れるが、DFSは遠い頂点から順に訪れるため 頂点の高さ ℎ𝑣 が大きくなりやすい ℎ𝑣 （BFS木） ℎ𝑣 （DFS木）
8. ④ DFSの探索順を工夫する 𝐴𝑣 が大きい頂点はできるだけ ℎ𝑣 を高くしたい DFSで 𝑨𝒗 が小さい頂点から順に探索するようにするとスコアが上がる 69,853,969点 （本番322位相当） 10 × 1 + 90 × 2 +50 × 3 + 30 × 4 = 460点 10 × 1 + 30 × 2 +50 × 3 + 90 × 4 = 580点 𝐴𝑣 の降順に探索 𝐴𝑣 の昇順に探索 10 30 90 50 10 30 90 50
9. ⑤ 根を全探索して貪欲 今まで根を適当に決めていたが、できるだけ効率良く頂点を使いたい 根を全探索して、 木のスコア÷木の頂点数 が最も大きい根を採用する貪欲 72,646,442点 （本番131位相当） 10 30 90 50 10 30 90 50 を根とする 520 ÷ 4 = 130点 を根とする 10 580 ÷ 4 = 145点 30
10. ⑥ 根の順番を焼きなまし 採用する根を貪欲に決めていたが、焼きなましで決めることもできる 根の列を解とし、順番にDFSを行うことで森を構築する 74,282,453点 （本番64位相当） 10 30 90 50 10 30 90 50 210 + 30 = 240点 250 + 50 = 300点 90 50 30 10 10 90 50 30 10
11. 解法例2 : 木を直接焼きなまし
12. ⑦ 木を直接焼きなまし 各頂点の親の頂点を解として焼きなまし 頑張って高速化すると 𝑂 𝐻 + 部分木の大きさ くらいで差分更新が可能 76,105,950点 （本番19位相当） 10 30 90 50 10 30 90 50 0 1 2 3 −1, 0, 0, 2 → 400点 0 1 2 3 −1, 0, 3, 1 → 580点
13. ⑦ 木を直接焼きなまし – 高速化 スコアの差分更新および木の高さ制限チェックに必要な情報を持つ 各頂点に 𝒉𝒗 ・親・子・部分木の𝑨𝒗 の和・部分木の最大𝒉𝒗 を持たせる ℎ = 3 ℎ = 2 ℎ = 1 ℎ = 0 Δ = ෍ 𝑣∈𝑇 ℎ𝑣 ′ + 1 𝐴𝑣 − ෍ 𝑣∈𝑇 ℎ𝑣 + 1 𝐴𝑣 = Δℎ𝑟𝑜𝑜𝑡 ෍ 𝑣∈𝑇 𝐴𝑣 スコア差分計算 max 𝑣∈𝑇 ℎ𝑣 + Δℎ𝑟𝑜𝑜𝑡 ≤ 𝐻 木の高さ制限チェック (部分木の𝑨𝒗 の和) (部分木の最大𝒉𝒗 ) ℎ𝑟𝑜𝑜𝑡
14. ⑦ 木を直接焼きなまし – 高速化 焼きなましが受理されたら祖先と部分木の 𝒉𝒗 ・親・子・部分木の𝑨𝒗 の和・部分木の最大𝒉𝒗 を更新する ℎ = 3 ℎ = 2 ℎ = 1 ℎ = 0
15. ⑧ 高さ制限違反を許容 高さ制限を常に守るようにすると遷移が成功しづらい 高さ制限違反を許容し、違反量に応じたペナルティをかけるとスコアが伸びる 76,858,739点 （本番2位相当） ℎ = 3 ℎ = 2 ℎ = 1 ℎ = 0 0 0.5 1 ペナルティ量 時刻 𝑠𝑐𝑜𝑟𝑒 = 1 + ෍ 𝑣 ℎ𝑣 + 1 𝐴𝑣 −𝛼1−𝑡𝛽𝑡 ෍ 𝑣 max ℎ𝑣 − 𝐻, 0 ペナルティは時間とともに 少しずつ大きくする