競プロ典型90問難易度4
AtCoder
競プロ典型90問
競プロ典型90問とその類題
競プロ典型90問難易度4
数え上げ問題
文字列
部分列
DP状態:フェーズ(耳DP)
DP
DP状態:照合文字列の何文字目まで到達したか
そのまま覚えたい典型問題
ナップサックDP
これまたすごく典型的な DP!!! 「状態遷移」を意識して取り扱う DP。ごく一部の界隈では耳 DP と呼ばれていたりもするかもしれない。 問題へのリンク editorial この問題の前提知識 ナップサック問題を解く DP が自力で書けること 1000000007 で割ったあ…
AtCoder
木
直径
サイクル
DFS
グラフ
競プロ典型90問
競プロ典型90問難易度4
競プロ典型90問とその類題
Python
【問題集】木の探索
【問題集】DFS・BFSのステップアップ
木の直径
木の直径を求めよ、という問題。直径を考えると解ける問題は高難易度でもお馴染みですね。 問題へのリンク editorial 類題とか drken1215.hatenablog.com 問題概要 頂点数 の木が与えられます。 この木に新たに辺を 1 本追加すると、閉路が 1 つできます。 …
AtCoder
二分探索
Greedy
最大値の最小化
最大スコア
N個からK個を選ぶ設定の問題
一直線上のN点の問題
競プロ典型90問
競プロ典型90問難易度4
競プロ典型90問とその類題
Python
【問題集】二分探索の入門
最適化問題
「最小値の最大化」には二分探索が有効という典型ですね。 問題へのリンク 解説へのリンク 前提知識 二分探索にまったく経験がない場合は、まずは次の記事を読んでみてください。 qiita.com 問題概要 長さ のようかんがあって、そのうち左端から の位置に切…