トポロジカルソートの数え上げ
楽しかったので。 問題概要 1 から 13 までの数字が書かれたカードが 1 枚ずつある。これをよくシャッフルして山札として並べて、1 枚ずつ引く。 このとき、引いたカードが「手札カードの数値の最大値」よりも小さかったらそのカードを捨て、そうでなかった…
AtCoder
AGC-F
数え上げ問題
操作によって何通りできるかの数え上げ問題
操作
条件の言い換え
問題の構造をわかりやすく特徴付ける
二項係数
DP
区間分割型ナップサックDP
探索順序を工夫して解く
選択肢が広い方か狭い方から決めていく
トポロジカルソートの数え上げ
挿入DP
DP高速化
DP高速化: 累積和
AtCoder1600~1900点
重複を防ぐ場合分けのテクニック
判定関数を考える
個数のみわかれば遷移が作れるDP
すごく楽しかった。 問題へのリンク 問題概要 色 のボールがそれぞれ 個ずつあります。 個のボールを好きな順序で並べ、各色について最も左側にあるボールを色 へと塗り替えました。 最終的な色の並びとして考えられる個数を 1000000007 で割ったあまりを求…
AtCoder
AtCoder1200点
ARC-F
企業コン
数え上げ問題
トポロジカルソートの数え上げ
グラフや盤面の数え上げ問題
グラフ問題
最小全域木
bitDP
順列の数え上げ問題
総和を求める
高速ゼータ変換
探索順序を工夫して解く
選択肢が広い方か狭い方から決めていく
挿入DP
前処理
DFS
サイクル
こういうの素早く解けるようになりたいね。 いわゆる「トポロジカルソート順の数え上げ」という高難易度でたまに見るパターンの問題。 問題へのリンク 問題概要 頂点 辺の無向グラフが与えられる。ここで、辺 が全域木を形成していることが保証されている。 …