典型タグ

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
分類・前提・学習成果

分類と直接の前提

概念上の親: 更新可能な最小十分要約

    関連する典型

      学習成果と学習単位

      代表問題

      この典型の考え方を具体的な問題で確かめるための入口です。

      関連問題

      この典型が主タグまたは補助タグとして付いている問題です。