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
730
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
2
1k
月刊 競技プログラミングをお仕事に役立てるには
terryu16
2
1.4k
AHC035解説
terryu16
0
1.3k
TOYOTA AHC 至高のアルゴリズム解説会 - Transit Warehouse 解説
terryu16
0
1.9k
AHC028解説
terryu16
0
1k
メタヒューリスティクスで広がる「解けた!」の世界
terryu16
12
5.7k
AHC020解説
terryu16
0
1.6k
Other Decks in Programming
See All in Programming
Django for Data Science (Boston Python Meetup, March 2025)
wsvincent
0
230
php-fpm がリクエスト処理する仕組みを追う / Tracing-How-php-fpm-Handles-Requests
shin1x1
5
810
requirements with math
moony
0
520
PHPでお金を扱う時、終わりのない 謎の1円調査の旅にでなくて済む方法
nakka
3
980
CTFのWebにおける⾼難易度問題について
hamayanhamayan
1
950
技術好きなエンジニアが "リーダーへの進化" によって得たものと失ったもの
pospome
5
1.3k
ステートソーシング型イベント駆動の視点で捉えるCQRS+ES
shinnosuke0522
1
310
Firebase Dynamic Linksの代替手段を自作する / Create your own Firebase Dynamic Links alternative
kubode
0
170
snacks.nvim内のセットアップ不要なプラグインを紹介 / introduce_snacks_nvim
uhooi
0
320
小さく段階的リリースすることで深夜メンテを回避する
mkmk884
2
120
複雑なフォームと複雑な状態管理にどう向き合うか / #newt_techtalk vol. 15
izumin5210
4
2.7k
英語文法から学ぶ、クリーンな設計の秘訣
newnomad
1
270
Featured
See All Featured
Making Projects Easy
brettharned
116
6.1k
KATA
mclloyd
29
14k
VelocityConf: Rendering Performance Case Studies
addyosmani
328
24k
GraphQLとの向き合い方2022年版
quramy
45
14k
A designer walks into a library…
pauljervisheath
205
24k
The Art of Programming - Codeland 2020
erikaheidi
53
13k
Building an army of robots
kneath
304
45k
Code Reviewing Like a Champion
maltzj
521
39k
Distributed Sagas: A Protocol for Coordinating Microservices
caitiem20
331
21k
Understanding Cognitive Biases in Performance Measurement
bluesmoon
27
1.6k
GitHub's CSS Performance
jonrohan
1030
460k
Building a Modern Day E-commerce SEO Strategy
aleyda
39
7.2k
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 ペナルティは時間とともに 少しずつ大きくする