被覆する方法の数え上げ
AtCoder
AtCoder1100点
DP
DP状態削減テク:全部分集合でなく個数のみ持つ
挿入DP
探索順序を工夫して解く
包除原理
数え上げ問題
被覆する方法の数え上げ
区間
ナップサックDP
選択肢が広い方か狭い方から決めていく
調和級数
見積り大事
二項係数
被覆
ARC-like
赤色diff
ARC-E
区間の連結関係に関する問題
高度典型
思わず解きたくなる興味深い良問
個人的要復習
固定長区間が制約条件を持ちながら左右に移動する問題
N個の区間の問題
すごく面白かった！！！！！！！ 問題へのリンク 問題概要 長さ のマス目があって、長さがそれぞれ の 個の区間を配置していきたい。 個の区間がすべてのマスを被覆するような配置方法は何通りあるか、1000000007 で割ったあまりを求めよ。 制約 考えたこと …
Codeforces
期待値
競技数学色強め
連続量問題
期待値の線形性
順列の数え上げ
DP
箱根駅伝DP
区間
被覆する方法の数え上げ
二項係数
数え上げ問題
被覆
図形的量の期待値
CodeforcesDIV2
CodeforcesR2800
こういうのに慣れて行きたい。 問題へのリンク 問題概要 長さ の線分上に、ランダムな区間を 個とったときの、区間が 本以上重なっている部分の長さの期待値を求めよ (998244353 で割った余りの形式で)。 なお、区間のランダムな選び方とは、線分から 2 点ず…
AtCoder
AtCoder700点
unrated公式コン
数え上げ問題
DP
包除原理
ナップサックDP
二項係数
区間
操作
操作:区間
被覆する方法の数え上げ
ダブルカウントを防ぐ場合分け
操作:上書き
補集合を考える
被覆
区間の連結関係に関する問題
解空間:O(2^N)通りの選択肢
700 点は絶対落とさないようにしたい！！！ 本番、DP と包除原理の二通りの方針が早期に見えて、「どちらかで詰まったらどちらかに立ち戻ろう」と思いながら DP に突き進んで見た。それでちゃんと通ってよかった。 問題へのリンク 問題概要 長さ の区間があ…
