O(3^N)なbitDP
AtCoder
AtCoder600点
黄色diff
ARC-D
彩色問題
グラフ
数学(整数問題)
数列
構築
Yes/No判定問題
区間
ほとんどのところで値が一定値に決まる
累積和テク:区間の総和を累積和で高速に求める
条件の言い換え
高速ゼータ変換
包除原理
O(3^N)なbitDP
bitDP
コンテスト後に解いた。こっちの方が解きやすかった。 問題へのリンク 問題概要 制約 考えたこと 最初は の指数を気にするのかな......などと考えていたが、考えていくうちに の値など、ただの飾りであることがわかってきた。 まず、問題の条件を言い換える…
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
AtCoder400点
水色diff
ABC-D
全探索
グラフ
グルーピング
グルーピングの数え上げ問題
数え上げ問題
全探索:再帰関数
DP
bitDP
O(3^N)
順列の数え上げ
見積り大事
制約条件:共演NG
O(3^N)なbitDP
典型要素を詰め合わせた教育的問題
全探索:再帰関数(ビット全探索困難)
【問題集】DFS・BFSのステップアップ
再帰関数を使った全探索が書けるかどうかが試される! 問題へのリンク 問題概要 人のスポーツ選手を 個のグループに分けたい。 ただし、仲の悪いスポーツ選手の組が 組ある。任意の に対して、選手 と選手 を同じグループに属させてはならない。 この制約を…