包除原理に関するメモ
余事象を考えて包除原理を用いる問題に出会う度、理解に時間がかかるのでメモ。
「すべて～ない」などの条件をもった場合の数を直接求めるのは難しく、否定の条件を考えて余事象で求めることがある。
例えば、求める条件が任意の に対して
であるというときに
という条件を考える、など。
否定の条件を禁止事項と呼ぶことにする。
E - NEQ や F - Heights and Pairs のように、禁止事項の個数で状態がまとめられるとき、少なくとも 個禁止事項を持つ集合を
(要素数 :
) とする。
に関して重要なのは、禁止事項以外は自由に決められるので
個より多く禁止事項を持つ可能性がある。(このおかげで数えやすい。)
また、全事象は禁止事項 個以上とも取れるので
である。
求める場合の数は全事象から禁止事項を持つ場合の数を引いたものであるので、禁止事項の個数の上限を とすると、
(∵包除原理)
と表せる。
アルゴリズムの簡単なまとめ Wiki - yukicoder にあるように、
と捉えるのは簡潔ですごい。
ただ、自分は まわりをどう捉えればいいか分からなくなってしまったので、ひとまず前述の形で理解することにした。
