Upgrade to Pro
— share decks privately, control downloads, hide ads and more …
Speaker Deck
Features
Speaker Deck
PRO
Sign in
Sign up for free
Search
Search
AHC041解説
Search
terry-u16
January 19, 2025
Programming
1
840
AHC041解説
AtCoder Heuristic Contest 041(
https://atcoder.jp/contests/ahc041
)の解説放送で使用した解説スライドです。
terry-u16
January 19, 2025
Tweet
Share
More Decks by terry-u16
See All by terry-u16
AtCoder Heuristic First-step Vol.1 講義スライド
terryu16
3
1.6k
月刊 競技プログラミングをお仕事に役立てるには
terryu16
2
1.5k
AHC035解説
terryu16
0
1.4k
TOYOTA AHC 至高のアルゴリズム解説会 - Transit Warehouse 解説
terryu16
0
2k
AHC028解説
terryu16
0
1.1k
メタヒューリスティクスで広がる「解けた!」の世界
terryu16
12
6.2k
AHC020解説
terryu16
0
1.7k
Other Decks in Programming
See All in Programming
try-catchを使わないエラーハンドリング!? PHPでResult型の考え方を取り入れてみよう
kajitack
3
520
Prism.parseで 300本以上あるエンドポイントに 接続できる権限の一覧表を作ってみた
hatsu38
1
110
コードの90%をAIが書く世界で何が待っているのか / What awaits us in a world where 90% of the code is written by AI
rkaga
39
26k
Haskell でアルゴリズムを抽象化する / 関数型言語で競技プログラミング
naoya
17
4.7k
CSC307 Lecture 17
javiergs
PRO
0
120
来たるべき 8.0 に備えて React 19 新機能と React Router 固有機能の取捨選択とすり合わせを考える
oukayuka
2
790
人には人それぞれのサービス層がある
shimabox
3
680
Beyond Portability: Live Migration for Evolving WebAssembly Workloads
chikuwait
0
380
Benchmark
sysong
0
210
Kotlin エンジニアへ送る:Swift 案件に参加させられる日に備えて~似てるけど色々違う Swift の仕様 / from Kotlin to Swift
lovee
1
230
都市をデータで見るってこういうこと PLATEAU属性情報入門
nokonoko1203
1
510
既存デザインを変更せずにタップ領域を広げる方法
tahia910
1
230
Featured
See All Featured
[RailsConf 2023 Opening Keynote] The Magic of Rails
eileencodes
29
9.5k
Keith and Marios Guide to Fast Websites
keithpitt
411
22k
jQuery: Nuts, Bolts and Bling
dougneiner
63
7.8k
Faster Mobile Websites
deanohume
307
31k
Building Adaptive Systems
keathley
43
2.6k
Practical Tips for Bootstrapping Information Extraction Pipelines
honnibal
PRO
20
1.3k
Fireside Chat
paigeccino
37
3.5k
The Illustrated Children's Guide to Kubernetes
chrisshort
48
50k
Rails Girls Zürich Keynote
gr2m
94
14k
Sharpening the Axe: The Primacy of Toolmaking
bcantrill
43
2.4k
Templates, Plugins, & Blocks: Oh My! Creating the theme that thinks of everything
marktimemedia
31
2.4k
The Art of Programming - Codeland 2020
erikaheidi
54
13k
Transcript
AHC041 解説 2025/1/19 writer : terry_u16
簡単な考察: どのような木が望ましいか 高い場所にあるほどスコアにかかる倍率が上がる できるだけ高い場所にたくさん頂点があるような木を作りたい ℎ = 0 ℎ = 1
ℎ = 2 ℎ = 3 低スコア 高スコア
解法例1 : DFSベース解法
① とりあえずACする 全ての頂点を根(-1)とする 7,584,268点 (本番954位相当)
② BFS木を作る まだ使われていない頂点を根として、BFS木を作る貪欲 55,988,632点 (本番741位相当) BFS中、頂点𝑢から頂点𝑣に 移動するときに辺を張ると 木ができる
③ DFS木を作る まだ使われていない頂点を根として、DFS木を作る貪欲 67,252,287点 (本番455位相当) DFS中、頂点𝑢から頂点𝑣に 移動するときに辺を張ると 木ができる
BFS木とDFS木 BFS木よりDFS木の方がスコアが高い BFSは近い頂点から順に訪れるが、DFSは遠い頂点から順に訪れるため 頂点の高さ ℎ𝑣 が大きくなりやすい ℎ𝑣 (BFS木) ℎ𝑣 (DFS木)
④ 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
⑤ 根を全探索して貪欲 今まで根を適当に決めていたが、できるだけ効率良く頂点を使いたい 根を全探索して、 木のスコア÷木の頂点数 が最も大きい根を採用する貪欲 72,646,442点 (本番131位相当) 10 30
90 50 10 30 90 50 を根とする 520 ÷ 4 = 130点 を根とする 10 580 ÷ 4 = 145点 30
⑥ 根の順番を焼きなまし 採用する根を貪欲に決めていたが、焼きなましで決めることもできる 根の列を解とし、順番に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
解法例2 : 木を直接焼きなまし
⑦ 木を直接焼きなまし 各頂点の親の頂点を解として焼きなまし 頑張って高速化すると 𝑂 𝐻 + 部分木の大きさ くらいで差分更新が可能 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点
⑦ 木を直接焼きなまし – 高速化 スコアの差分更新および木の高さ制限チェックに必要な情報を持つ 各頂点に 𝒉𝒗 ・親・子・部分木の𝑨𝒗 の和・部分木の最大𝒉𝒗 を持たせる
ℎ = 3 ℎ = 2 ℎ = 1 ℎ = 0 Δ = 𝑣∈𝑇 ℎ𝑣 ′ + 1 𝐴𝑣 − 𝑣∈𝑇 ℎ𝑣 + 1 𝐴𝑣 = Δℎ𝑟𝑜𝑜𝑡 𝑣∈𝑇 𝐴𝑣 スコア差分計算 max 𝑣∈𝑇 ℎ𝑣 + Δℎ𝑟𝑜𝑜𝑡 ≤ 𝐻 木の高さ制限チェック (部分木の𝑨𝒗 の和) (部分木の最大𝒉𝒗 ) ℎ𝑟𝑜𝑜𝑡
⑦ 木を直接焼きなまし – 高速化 焼きなましが受理されたら祖先と部分木の 𝒉𝒗 ・親・子・部分木の𝑨𝒗 の和・部分木の最大𝒉𝒗 を更新する ℎ
= 3 ℎ = 2 ℎ = 1 ℎ = 0
⑧ 高さ制限違反を許容 高さ制限を常に守るようにすると遷移が成功しづらい 高さ制限違反を許容し、違反量に応じたペナルティをかけるとスコアが伸びる 76,858,739点 (本番2位相当) ℎ = 3 ℎ
= 2 ℎ = 1 ℎ = 0 0 0.5 1 ペナルティ量 時刻 𝑠𝑐𝑜𝑟𝑒 = 1 + 𝑣 ℎ𝑣 + 1 𝐴𝑣 −𝛼1−𝑡𝛽𝑡 𝑣 max ℎ𝑣 − 𝐻, 0 ペナルティは時間とともに 少しずつ大きくする