部分集合・bitmask状態DP
各bitの意味を固定し、訪問集合・選択集合・frontierなどの部分集合状態間を遷移する。
この典型を扱う単元: 部分集合・bitmask状態DP
検索別名: bitmask DP、subset DP、部分集合DP
未知問からこの典型を見つける手掛かり
- 扱う対象
- bitmask
- 訪問集合
- 部分集合
- 使う手掛かり
- submask
- 小さいN
- 集合状態
- 保つ不変量
- bitの意味
- 集合包含
- 求めるもの
- 全訪問
- 部分集合状態
- 適用しない条件
- 個別の除外条件の記載はありません。扱う対象と使う手掛かりから適用を判断してください。
分類・前提・学習成果
分類と直接の前提
概念上の親: DP状態と遷移
関連する典型
- frontier/profile DP・境界状態圧縮: 集合の使用済みフラグを状態にする点は共通する。境界DPでは未来へ影響しない要素を忘れ、指数部分を全要素数ではなく境界幅に限定できることをさらに証明する。
学習成果と学習単位
bitmaskの各bitが表す意味を定め、部分集合間の遷移を正しく設計できる。
部分集合・bitmask状態DPで学ぶ
代表問題
この典型の考え方を具体的な問題で確かめるための入口です。
関連問題
この典型が主タグまたは補助タグとして付いている問題です。
- ABC213 G「Connectivity 2」 公式問題主題: label付き連結成分分解・exponential formula / 補助タグ
技能・出典
主題: label付き連結成分分解・exponential formula
主タグ: label付き連結成分分解・exponential formula / 補助タグ: 部分集合・bitmask状態DP
- ABC215 E「Chain Contestant」 公式問題主題: 最小十分状態からDPを設計する / 補助タグ
- ABC216 H「Random Robots」 公式問題主題: 行列式による数え上げ / 補助タグ
- ABC228 G「Digits on Grid」 公式問題主題: 非決定性automatonのsubset construction / 補助タグ
- ABC232 F「Simple Operations on Sequence」 公式問題主題: 部分集合・bitmask状態DP / 主タグ
- ABC274 E「Booster」 公式問題主題: 部分集合・bitmask状態DP / 主タグ
- ABC278 F「Shiritori」 公式問題主題: ゲーム状態の勝敗とGrundy数 / 補助タグ
- ABC301 E「Pac-Takahashi」 公式問題主題: 部分集合・bitmask状態DP / 主タグ
- ABC306 Ex「Balance Scale」 公式問題主題: 包除・Möbius反転で重複を補正する / 補助タグ
- ABC309 G「Ban Permutation」 公式問題主題: 包除・Möbius反転で重複を補正する / 補助タグ
技能・出典
主タグ: 集合上の包除原理 / 補助タグ: 組合せ係数・数え上げ、frontier/profile DP・境界状態圧縮、部分集合・bitmask状態DP
- ABC310 F「Make 10 Again」 公式問題主題: 部分集合・bitmask状態DP / 主タグ
- ABC313 F「Flip Machines」 公式問題主題: 候補数を界して全列挙・有限case分解する / 補助タグ
- ABC319 F「Fighter Takahashi」 公式問題主題: 部分集合・bitmask状態DP / 主タグ
- ABC321 G「Electric Circuit」 公式問題主題: label付き連結成分分解・exponential formula / 補助タグ
- ABC328 G「Cut and Reorder」 公式問題主題: 部分集合・bitmask状態DP / 主タグ
- ABC332 E「Lucky bag」 公式問題主題: 部分集合・bitmask状態DP / 主タグ
- ABC338 F「Negative Traveling Salesman」 公式問題主題: 部分集合・bitmask状態DP / 主タグ
- ABC343 G「Compress Strings」 公式問題主題: 部分集合・bitmask状態DP / 主タグ
- ABC352 F「Estimate Order」 公式問題主題: 部分集合・bitmask状態DP / 主タグ
- ABC354 E「Remove Pairs」 公式問題主題: ゲーム状態の勝敗とGrundy数 / 補助タグ
- ABC381 F「1122 Subsequence」 公式問題主題: 部分集合・bitmask状態DP / 主タグ
- ABC396 G「Flip Row or Col」 公式問題主題: 部分集合・bitmask状態DP / 主タグ
- ABC400 G「Patisserie ABC 3」 公式問題主題: Lagrangian relaxation・Aliens trick / 補助タグ
技能・出典
主題: Lagrangian relaxation・Aliens trick
主タグ: Lagrangian relaxation・Aliens trick / 補助タグ: 部分集合・bitmask状態DP
- ABC402 E「Payment Required」 公式問題主題: 確率過程・期待値DP / 補助タグ
- ABC411 G「Count Cycles」 公式問題主題: 部分集合・bitmask状態DP / 主タグ
- ABC419 F「All Included」 公式問題主題: Aho–Corasick / 補助タグ
- ABC425 F「Inserting Process」 公式問題主題: 部分集合・bitmask状態DP / 主タグ
- ABC432 F「Candy Redistribution」 公式問題主題: 部分集合・bitmask状態DP / 主タグ