bitsetによるword並列集合演算
真偽集合をbit列へ詰め、交差・和・shift・popcountをword単位で実行して遷移や組数計算を加速する。
この典型を扱う単元: bitsetで集合演算をword並列化する
検索別名: bitset optimization、word-parallel algorithm、ビット集合
未知問からこの典型を見つける手掛かり
- 扱う対象
- bit列
- 真偽配列
- 隣接集合
- 集合
- 使う手掛かり
- bitset.*and
- word単位
- 一括shift
- 集合の積
- 保つ不変量
- popcount
- word幅
- 各bitが要素
- 求めるもの
- 共通要素数
- 到達集合
- 遷移高速化
- 適用しない条件
- binary indexed tree
- fenwick
分類・前提・学習成果
分類と直接の前提
概念上の親: 更新可能な最小十分要約
関連する典型
学習成果と学習単位
集合をbit列へ符号化し、交差・和・shift・popcountをword並列に実行した計算量を評価できる。
bitsetで集合演算をword並列化するで学ぶ
代表問題
この典型の考え方を具体的な問題で確かめるための入口です。
関連問題
この典型が主タグまたは補助タグとして付いている問題です。
- ABC221 G「Jumping sequence」 公式問題主題: bitsetで集合演算をword並列化する / 主タグ
- ABC258 G「Triangle」 公式問題主題: bitsetで集合演算をword並列化する / 主タグ
- ABC276 Ex「Construct a Matrix」 公式問題主題: 線形方程式・rank / 補助タグ
- ABC287 Ex「Directed Graph and Query」 公式問題主題: 推移閉包 / 補助タグ
- ABC348 F「Oddly Similar」 公式問題主題: bitsetで集合演算をword並列化する / 主タグ
- ABC366 G「XOR Neighbors」 公式問題主題: 線形方程式・rank / 補助タグ
- ABC430 G「Range Set Modifying Query」 公式問題主題: Segment Tree Beats / 補助タグ