制約条件:共演NG
最小添字規則によってダブルカウントを防ぐ
対象を一意に定める操作列を数え上げる
AtCoder
AtCoder400点
水色diff
ABC-D
全探索
グラフ
グルーピング
グルーピングの数え上げ問題
数え上げ問題
全探索:再帰関数
DP
bitDP
O(3^N)
順列の数え上げ
見積り大事
制約条件:共演NG
O(3^N)なbitDP
典型要素を詰め合わせた教育的問題
【問題集】ビット全探索が困難な再帰全探索問題
【問題集】DFS・BFSのステップアップ
再帰関数を使った全探索が書けるかどうかが試される! 問題へのリンク 問題概要 人のスポーツ選手を 個のグループに分けたい。 ただし、仲の悪いスポーツ選手の組が 組ある。任意の に対して、選手 と選手 を同じグループに属させてはならない。 この制約を…
DP
DP高速化
DP高速化:累積和
累積和
ナップサックDP
区間
区間分割型ナップサックDP
AOJ
AtCoder
JOI予選
JOI
JOI難易度7
累積max
制約条件:区間
区間ソート
そのまま覚えたいシンプル設定の中堅以上の典型問題
最大スコア
解空間:O(2^N)通りの選択肢
制約条件:共演NG
最適化問題
区間についてどうのこうのする問題、大抵は DP! 問題へのリンク 問題概要 個の整数 がある。これらのうちいくつか選んだ合計を最大化したい。ただし、 の区間 [ ] があって、選んだ数のどの 2 つをとっても同一区間上にならないようにしなければならない。 …