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