utsubo’s blog

競技プログラミングとか.

グラフ理論系の好きな問題 5選

最近何もする気が起きないので,今までに見た数少ない問題の中で好きだった問題を紹介します(脚注にネタバレ).

1. TopCoder Single Round Match 642 Div.2 Hard Tall Shoes

*1が好きなので好きです.
https://community.topcoder.com/stat?c=problem_statement&pm=13523
TopCoder SRM 642 Div2 Hard TallShoes - kmjp's blog

2. Indeedなう A日程 D: Longest Path

全然わからなかったけど,解説を読んで実装するのが楽しかった.
D: Longest Path - Indeedなう(オープンコンテスト) | AtCoder
Indeedなう A日程 解説

4. CODE FESTIVAL 2015 決勝 I: 風船ツリー

これも実装が楽しい問題でした.
I: 風船ツリー - CODE FESTIVAL 2015 決勝(オープンコンテスト) | AtCoder
CODE FESTIVAL 2015 解説 - SSSSLIDE

まとめ

グラフ理論系の問題は実装が楽しいものが多くて好きです.
なんか最近の問題が多くて申し訳ない感じになりました.
手を付けてない組み合わせ系の問題に取り組みたい.






以下,問題の解法ネタバレ.

*1:二分探索

*2:最短経路問題

*3:フロー