競プロ典型90問難易度4
これまたすごく典型的な DP！！！ 「状態遷移」を意識して取り扱う DP。ごく一部の界隈では耳 DP と呼ばれていたりもするかもしれない。 問題へのリンク editorial この問題の前提知識 ナップサック問題を解く DP が自力で書けること 1000000007 で割ったあ…
木の直径を求めよ、という問題。直径を考えると解ける問題は高難易度でもお馴染みですね。 問題へのリンク editorial 類題とか drken1215.hatenablog.com 問題概要 頂点数 の木が与えられます。 この木に新たに辺を 1 本追加すると、閉路が 1 つできます。 …
AtCoder
二分探索
Greedy
最大値の最小化
最大スコア
N個からK個選んだものの最適化
一直線上のN点の問題
競プロ典型90問
競プロ典型90問難易度4
競プロ典型90問とその類題
Python
「最小値の最大化」 (or 「最大値の最小化」) には二分探索が有効という典型ですね。 類題とか (二分探索以外の問題も含むことと、ハイレベルな問題も多いことに注意) drken1215.hatenablog.com 問題へのリンク 解説へのリンク 問題概要 長さ のようかんがあ…
