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
810
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.5k
月刊 競技プログラミングをお仕事に役立てるには
terryu16
2
1.5k
AHC035解説
terryu16
0
1.4k
TOYOTA AHC 至高のアルゴリズム解説会 - Transit Warehouse 解説
terryu16
0
2k
AHC028解説
terryu16
0
1.1k
メタヒューリスティクスで広がる「解けた!」の世界
terryu16
12
6k
AHC020解説
terryu16
0
1.7k
Other Decks in Programming
See All in Programming
Devinで実践する!AIエージェントと協働する開発組織の作り方
masahiro_nishimi
6
1.8k
REST API設計の実践 – ベストプラクティスとその落とし穴
kentaroutakeda
2
230
SpringBootにおけるオブザーバビリティのなにか
irof
1
850
TypeScriptのmoduleオプションを改めて整理する
bicstone
4
380
TSConfig Solution Style & subpath imports to switch types on a per-file basis
maminami373
1
160
イベントソーシングとAIの親和性ー物語とLLMに理解できるデータ
tomohisa
1
150
少数精鋭エンジニアがフルスタック力を磨く理由 -そしてAI時代へ-
rebase_engineering
0
100
Boast Code Party / RubyKaigi 2025 After Event
lemonade_37
0
300
AI時代のリアーキテクチャ戦略 / Re-architecture Strategy in the AI Era
dachi023
0
180
CursorとDevinが仲間!?AI駆動で新規プロダクト開発に挑んだ3ヶ月を振り返る / A Story of New Product Development with Cursor and Devin
rkaga
5
1.8k
AIにコードを生成するコードを作らせて、再現性を担保しよう! / Let AI generate code to ensure reproducibility
yamachu
7
5.6k
Interface vs Types ~型推論が過多推論~
hirokiomote
1
190
Featured
See All Featured
Measuring & Analyzing Core Web Vitals
bluesmoon
7
450
Large-scale JavaScript Application Architecture
addyosmani
512
110k
Creating an realtime collaboration tool: Agile Flush - .NET Oxford
marcduiker
30
2.1k
Site-Speed That Sticks
csswizardry
6
570
It's Worth the Effort
3n
184
28k
Art, The Web, and Tiny UX
lynnandtonic
298
21k
Typedesign – Prime Four
hannesfritz
41
2.6k
Designing Experiences People Love
moore
142
24k
Adopting Sorbet at Scale
ufuk
76
9.4k
Design and Strategy: How to Deal with People Who Don’t "Get" Design
morganepeng
129
19k
Bootstrapping a Software Product
garrettdimon
PRO
307
110k
Product Roadmaps are Hard
iamctodd
PRO
53
11k
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 ペナルティは時間とともに 少しずつ大きくする