bitによる集合管理

[zawa-tin]

名前

zawa::BitSet

概要

bit全探索や、bitdpでよくやる操作をクラス化する

参考

(履修に利用したサイト、なるべく細かく載せておく)

https://qiita.com/hamamu/items/2e342d46d9f54732d42c#bit%E6%93%8D%E4%BD%9C%E7%94%A8%E3%82%AF%E3%83%A9%E3%82%B9

https://luzhiled1333.github.io/comp-library/src/utility/bit/popcount.hpp

https://qiita.com/drken/items/7c6ff2aa4d8fce1c9361

https://www.slideshare.net/KMC_JP/slide-www

関連issue

verifyリンク

• https://atcoder.jp/contests/abc187/tasks/abc187_f
• https://atcoder.jp/contests/abc199/tasks/abc199_e
• https://atcoder.jp/contests/abc269/tasks/abc269_c
• https://atcoder.jp/contests/abc246/tasks/abc246_f

追加ファイル名

進行状況

• [ ] コードを書いた
• [ ] AtCoderかAOJでverify(書いたコードを利用してAC)した
• [ ] documentを書いた
• [ ] verifyコードの解説を書いた

[zawa-tin]

欲しい機能は何だろう

• 和集合、積集合、差集合を返す
• $0, 1, 2, \dots, 2^N - 1$ までをrange_based_forでやる
• 集合 $A$ が集合 $B$ の部分集合であるかを判定する
• lsb、rsbを返す。
• popcountを返す(sizeみたいな命名?)
• 補集合を返す

[zawa-tin]

集合の要素数を返すメソッド名

• cardinality
• size
• popcount どれもええなぁ。競プロ的にはsizeか？

[zawa-tin]

普通にcardか。はい..

[zawa-tin]

集合・位相(松阪) に習って和集合、積集合はjoin, meet

• unionが予約語で全てが破滅してる。

[zawa-tin]

後はべき集合の列挙なんですけど....

• cardの小さい順に列挙したい時とcardの大きい順に列挙したい時がある
• range-based forでやりたみがあるが、なかなか良い実装が思いつかない
• vectorで列挙しても良いが、MLEが怖い....

[zawa-tin]

サイズをテンプレート引数で指定するやつは一通り書いてみた。

任意サイズ.... help wanted案件だな。

• https://github.com/atcoder/ac-library/blob/master/atcoder/modint.hpp とかを読んで見る