包除原理
ある事象の場合の数を直接数えにくい場合に、より小さくてシンプルな数え上げに分割して解く問題分割。部分事象が排反である時は単なる足し算だが、そうでなくても、共通部分が求められるなら包除原理が使える。
| A \cup B | = |A| + |B| - |A \cap B|
バイナリ素性の組み合わせで表現するという解釈もできる。
000を求めたいが直接求めることが困難である時に、*** - (1** + *1* + **1) + (11* + 1*1 + *11) - (111) を計算する
特に1の個数kによって集合のサイズf(k)が決まる場合
\sum_k -1^k \binom{n}{k} f(k)
| \bigcap_{i \in V}A_i | = \sum_{S \subseteq V} (-1)^{|S|} | \bigcap_{i\in S} A_i^{\mathsf c} |
> |A or B| = |A| + |B| - |A and B|と考えるのではなく|¬A and ¬B| = |U| - |A| - |B| + |A and B|と考えると楽 src ABC172E
| A \cup B | = |A| + |B| - |A \cap B|
| A^{\mathsf c} \cap B^{\mathsf c} | = |U| - |A| - |B| + |A \cap B|
>事象にちゃんと名前をつけて式変形をする・どの事象が簡単に計算できるかを意識する
>今回のN=3とした場合を考える．#()で事象の要素数を表すとする．
> Pi = (Ai=Biとなる事象)として，求めたいのは#(¬P1 ∧ ¬P2 ∧ ¬P3)で，簡単に計算できるのは#(P1)とか#(P1 ∧ P2)とか．#(¬P1 ∧ ¬P2)とかは扱いにくいので，ドモルガンで#(¬(P1 ∨ P2 ∨ P3))に直して包除原理，と考えると簡単
包除原理 解ける数え上げの範囲を広げよう tsutaj
小さければ全探索
対称性によって組み合わせに帰着
O(2^N)がO(N)になる
部分集合それぞれについて包除原理を使うときO(3^N)
なぜ？ →部分集合の部分集合の数の和
これは重いI
高速メビウス変換はこれをO(N2^N)にできる
関連
Related Pages
- →ショーペンハウエル×エントロピー×難しい課題×全体を一つの問題だと考えている×問題分割×切り分け×この解決方法で解決できる部分はあるか？×その方法では解決できない→この方法で解決できる部分はどこか？×たとえ×問題解決×この問題は難しい→
- →僕のatcoderの学び方(〜青)×past5o×atcoder失敗リスト×abc175e×abc174f×ABC172E×abc178f×arc106c×arc106×arc105c×arc105d×arc104c×arc107d×貪欲法×最小カットに帰着→
- →僕のatcoderの学び方(〜水色)×僕のatcoderの学び方(〜PAST上級)×ABC187×past過去問練習202012×変形テクニックに名前をつける×頂点数18の制約×辺が10^5の制約×行列の半分×二項定理×足し算の順序の変更×辺が10^5ならダイクストラ使える×典型力×問題変換×問題分割×認知の解像度×概念のハンドル×atcoder失敗リスト×atcoderentrypoint×アルゴリズム実技検定×第五回_アルゴリズム実技検定×最小費用流に帰着×帰着訓練→
"Engineer's way of creating knowledge" the English version of my book is now available on [Engineer's way of creating knowledge]
(C)NISHIO Hirokazu / Converted from [Scrapbox] at [Edit]