記事の説明
・文の中に解法ネタバレがあるので初見の方は注意してください!!!
・競技プログラミングの問題で気に入ったものを独断と偏見で列挙していくだけの記事
・Atcoder茶上位~水色下位相当の難易度の問題が多い？
・随時更新中
問題
[1] ABC251E - Takahashi and Animals
DPを用いる問題, ナップザックDPの次に取り組むのが良さそう？
[2] パナソニックプログラミングコンテスト2020 C - Sqrt Inequality
浮動小数点の取り扱いには注意
[3] ABC212D - Querying Multiset
あまりにも賢こすぎる. 高度なデータ構造？いいえ必要ありません.
[4] ABC200D - Happy Birthday! 2
最初に解いたときはゴリ押しDPかと思った. 言われてみれば確かにとなる. 初見で気づける人凄い.
[5] ZONeエナジー プログラミングコンテスト “HELLO SPACE”C - MAD TEAM
最大値の最小化→アレ, その時の判定部分はどうやれば良い？
[6] ABC198E - Unique Color
情報を上手く持ってDFS
[7] ABC046C - AtCoDeerくんと選挙速報
少し数学寄りの問題？めちゃくちゃ場合分けするのかと思ったがそんなことはなかった.
[8] No.2232 Miser's Gift
ナップザックDPになにかをすれば良い.
[9] ABC105 D - Candy Distribution
典型的な数え上げらしい.
[10] ABC178C - Ubiquity
難しい...
[11] ABC194C - Squared Error
制約を見て
[12]ABC131E - Friendships
条件を満たすグラフを構築しろという問題.今まであまり見たことがない種類の問題.
[13]ABC040D - 道路の老朽化対策について
グラフの連結判定→アレ, そしてアレを使うためにはどうすれば良いか？
[14]ABC224D - 8 Puzzle on Graph
制約が小さめなので何らかの方法で全探索を行えそうな気がしたけどどうすればいいか分からなかった. 比較的簡単な解法の割に水diff中盤くらいなのであまり典型ではないのかもしれない(?).
[15]ABC202E - Count Descendants
根付き木に対するクエリを区間に対するクエリにするあのアルゴリズム!!!
[16]ABC167D - Teleporter
周期性を用いる解法に加えてもう１つの解法があるよ