🎰
競プロ 重要グラフ系アルゴリズム(ダイクストラ、ワーシャルフロイド、Union-Find)を使えるAtCoderの問題まとめ
素敵な夜ですね。
頻出グラフ系アルゴリズム(ダイクストラ、ワーシャルフロイド、Union-Find)を使えるABCの問題まとめを書きます。
類似記事多くありますが、別コンテストの例題が掲載されていることが多く、調べるのに苦労した為残しておきます。
ダイクストラ(Dijkstra)
応用が効く単一頂点から全頂点への最短距離導出アルゴリズム。
ABC214C Distribution
普通に解けばメモ化の実践問題だが、ちょうどよいダイクストラの基本問題となる。
ABC035D トレジャーハント
ダイクストラの応用問題、水diff最上位。難易度高
ワーシャルフロイド(Floyd–Warshall)
観測範囲においては、日本語ではワーシャルフロイドと呼ばれる事が多い。
英語ではFloyd–Warshallが一般的な様子なので、併記。
一定の出題頻度がある全頂点から全頂点への最短距離導出アルゴリズム。
ABC208 Shortest Path Queries 2
ワーシャルフロイドの基本問題。緑diff最上位。
ABC073 joisino's travel
ワーシャルフロイドの実践的な問題。また、(恐らく見て回った範囲では)ダイクストラでも解ける様子。水diff下位。
ABC074 Restoring Road Network
ワーシャルフロイドの応用問題。難易度高。水diff最上位。
Union-Find
応用が効く分類アルゴリズム。
AtCoder Typical Contest 001 Union Find
Union-Findの基本的な使い方を学習できる。
ABC177 Friends
Union-Findの基本問題。茶diff最上位。
各分類の構成要素数を判定する機能が必要となる。
ABC097D Equals
Union-Findの実践的な問題。水diff下位
ABC120 Decayed Bridges
Union-Findの実践的な問題。水diff下位
おわり
競プロ・Node.jsが好きな人は相互になってください twitter.com/kisihara_c
Discussion