除原理
AtCoder
AtCoder600点
橙色diff
ABC-G
除原理
数え上げ問題
高度典型
主客転倒
個別の要素の動きに注目する
指数探索系問題
DP
bitDP
O(3^N)
O(3^N)なbitDP
SubsetConvolution
集合冪級数(SPS)
SPSテク:f=log(exp(f))
解空間:O(N!)通りの選択肢
順列の数え上げ
グラフ
グラフ・盤面・数列の個数の数え上げ
グラフの頂点集合の部分集合を走査する
個人的要復習
期待値
期待値の線形性
線形性に着目する
連結成分
集合族に関する問題
最小添字規則によってダブルカウントを防ぐ
場合分け
除原理！ 学びの多い問題だった。Subset Convolution の方はちょっと頑張ってこの後復習する。 問題へのリンク 問題概要 頂点番号が であるグラフ がある。最初、辺は 1 本もない。 以上 以下の値からなるサイズ の 2 つの数列 と がある。 今、これら 2 つ…
AtCoder
AtCoder600点
ABC-G
橙色diff
部分グラフ列挙問題
数え上げ問題
グラフ
指数探索系問題
bitDP
高速ゼータ変換
グラフのconnectivity
グラフ・盤面・数列の個数の数え上げ
一般化した問題を解く
包除原理
除原理
グラフの頂点集合の部分集合を走査する
各kに対して
場合分け
SubsetConvolution
高速畳み込み計算
O(3^N)
補集合を考える
個人的要復習
面白かった！！ より一般化した問題 (グラフの頂点集合の任意の部分集合に対して、それらを連結にする辺の選び方の数え上げ) を考えた方が考えやすいね。 問題へのリンク 問題概要 頂点数 、辺数 の単純無向グラフ が与えられます。 の辺集合の部分集合 ( 通…
二次元グリッド
数え上げ問題
包除原理
DP
包除原理:DP
AtCoder
除原理
パリティ
DP状態:あまり
EDPCとTDPC
DP状態:パリティ
壁マス
DP状態削減テク:個数でなくパリティのみ持つ
座圧に見えてしまった 問題へのリンク 問題概要 のグリッドがあります。グリッドのうち マスに壁があって壁の位置は で与えられます。壁のあるマスには行けません。 マス からマス へと至る最短経路が何通りあるか、 で割ったあまりを求めよ。 制約 考えたこ…
