🎰

競プロ 重要グラフ系アルゴリズム(ダイクストラ、ワーシャルフロイド、Union-Find)を使えるAtCoderの問題まとめ

2021/09/09に公開

素敵な夜ですね。

頻出グラフ系アルゴリズム(ダイクストラ、ワーシャルフロイド、Union-Find)を使えるABCの問題まとめを書きます。
類似記事多くありますが、別コンテストの例題が掲載されていることが多く、調べるのに苦労した為残しておきます。

ダイクストラ(Dijkstra)

応用が効く単一頂点から全頂点への最短距離導出アルゴリズム。

ABC214C Distribution

https://atcoder.jp/contests/abc214/tasks/abc214_c

普通に解けばメモ化の実践問題だが、ちょうどよいダイクストラの基本問題となる。

ABC035D トレジャーハント

https://atcoder.jp/contests/abc035/tasks/abc035_d

ダイクストラの応用問題、水diff最上位。難易度高

ワーシャルフロイド(Floyd–Warshall)

観測範囲においては、日本語ではワーシャルフロイドと呼ばれる事が多い。
英語ではFloyd–Warshallが一般的な様子なので、併記。

一定の出題頻度がある全頂点から全頂点への最短距離導出アルゴリズム。

ABC208 Shortest Path Queries 2

https://atcoder.jp/contests/abc208/tasks/abc208_d

ワーシャルフロイドの基本問題。緑diff最上位。

ABC073 joisino's travel

https://atcoder.jp/contests/abc073/tasks/abc073_d

ワーシャルフロイドの実践的な問題。また、(恐らく見て回った範囲では)ダイクストラでも解ける様子。水diff下位。

ABC074 Restoring Road Network

https://atcoder.jp/contests/abc074/tasks/arc083_b

ワーシャルフロイドの応用問題。難易度高。水diff最上位。

Union-Find

応用が効く分類アルゴリズム。

AtCoder Typical Contest 001 Union Find

https://atcoder.jp/contests/atc001/tasks/unionfind_a

Union-Findの基本的な使い方を学習できる。

ABC177 Friends

https://atcoder.jp/contests/abc177/tasks/abc177_d

Union-Findの基本問題。茶diff最上位。
各分類の構成要素数を判定する機能が必要となる。

ABC097D Equals

https://atcoder.jp/contests/abc097/tasks/arc097_b

Union-Findの実践的な問題。水diff下位

ABC120 Decayed Bridges

https://atcoder.jp/contests/abc120/tasks/abc120_d

Union-Findの実践的な問題。水diff下位

おわり

競プロ・Node.jsが好きな人は相互になってください twitter.com/kisihara_c

Discussion