bitsetで集合演算をword並列化する
概要
bitsetによるword並列集合演算
真偽集合をbit列へ詰め、交差・和・shift・popcountをword単位で実行して遷移や組数計算を加速する。
考え方
真偽集合をwordへ詰め、AND・OR・shiftをw bitずつ処理する。集合演算、到達集合、部分和の遷移を多数のscalar更新からword単位へまとめる。
集合の要素iをword floor(i/w)のbit i mod wに置く。交差はAND、unionはOR、対称差はXOR、個数は各wordのpopcountの和。shift kではword移動q=floor(k/w)とbit移動r=k mod wへ分け、隣接二wordからrとw−r bitを合成する。r=0はword移動だけにしてword幅ちょうどのshiftを避け、最後のwordのM以降のpaddingを0へmaskする。
0/1部分和の到達集合ならbit0だけ1で始め、正の重さaを一個読むごとに bits←bits OR (oldBits<<a) とする。未選択と一回選択の二集合を合併する遷移である。in-placeでwordを処理する場合は高い方から更新して、同じ品物を二回使う伝播を防ぐ。bitset式の右辺が旧値から計算されることと、word実装の更新順を合わせる。
成立条件と計算量
M bitの一演算はO(⌈M/w⌉)。bitset操作をO(1)と数えない。shift後の範囲外bit、長さのpadding、in-place更新の意味を確認する。数え上げの多重度は真偽集合だけでは保存できない。
問題一覧
- ABC258 G「Triangle」 公式問題組合せ: 局所寄与へ分解して集計順を交換する
技能・出典
主題: bitsetで集合演算をword並列化する(集合をbit列へ符号化し、交差・和・shift・popcountをword並列に実行した計算量を評価できる。)。既習技能: 局所寄与へ分解して集計順を交換する(数える対象を要素・組・値・区間のいずれかで一意に固定し、各対象が含まれる回数または指示変数の期待値を先に求めて総和できる。)。主タグ: bitsetによるword並列集合演算 / 補助タグ: 寄与の数え上げと順序交換
- ABC348 F「Oddly Similar」 公式問題
技能・出典
主題: bitsetで集合演算をword並列化する(集合をbit列へ符号化し、交差・和・shift・popcountをword並列に実行した計算量を評価できる。)。主タグ: bitsetによるword並列集合演算
- ABC221 G「Jumping sequence」 公式問題
技能・出典
主題: bitsetで集合演算をword並列化する(集合をbit列へ符号化し、交差・和・shift・popcountをword並列に実行した計算量を評価できる。)。既習技能: 成立証明から構成解を復元する(成立証明に対応する親・局所操作・選択を記録し、要件を満たす構成を出力できる。) / 幾何の基本判定と座標変換(幾何条件を外積・距離式・端点順・格子占有・変換後座標の局所判定へ落とし込める。)。主タグ: bitsetによるword並列集合演算 / 補助タグ: 構成解・witness復元、幾何の基本判定・配置・座標変換
各問題の解説は問題ごとの本文として執筆します。各項目には主題・追加で学ぶ技能・既習技能の役割を示します。
関連問題
他の主題と組み合わせる問題を読む
以下はこのUnitのOutcomeを追加で学ぶ技能または既習技能として参照する、別のUnitを主題とする問題です。
- ABC276 Ex「Construct a Matrix」 公式問題主題: 線形方程式・rank
技能・出典
主題: 線形方程式・rank(制約を体上の連立一次方程式へ写し、Gaussian eliminationでrank・可解性・解空間次元を求める。その発動条件、正当性、計算量を説明し、未知問へ実装できる。)。既習技能: bitsetで集合演算をword並列化する(集合をbit列へ符号化し、交差・和・shift・popcountをword並列に実行した計算量を評価できる。) / 疎なkeyの順序を保ってdense indexへ圧縮する(初期値・将来更新値・疎なevent座標をsort-uniqueし、順序と等値性を保つdense indexまたは有限状態へ写せる。) / 一次元・二次元累積和と差分で区間情報を線形化する(prefix配列またはprefix変数を置き、区間和を二つのprefix値の差で表現できる。多次元の直方体は2^D隅の包除で取得し、一括加算は端点差分へ変換できる。) / 成立証明から構成解を復元する(成立証明に対応する親・局所操作・選択を記録し、要件を満たす構成を出力できる。)。主タグ: 線形方程式・rank / 補助タグ: bitsetによるword並列集合演算、構成解・witness復元、座標・値の順序保存圧縮、累積和・差分配列
- ABC287 Ex「Directed Graph and Query」 公式問題主題: 推移閉包
技能・出典
主題: 推移閉包(各始点探索または中継許可集合の段階不変条件を保つWarshall更新で推移閉包を求め、必要なら初回到達段階も記録できる。)。既習技能: bitsetで集合演算をword並列化する(集合をbit列へ符号化し、交差・和・shift・popcountをword並列に実行した計算量を評価できる。) / event順にactive集合を更新する(値・時刻・座標順にeventを並べ、同値eventの処理順とactive集合の増分更新を設計できる。)。主タグ: 推移閉包 / 補助タグ: bitsetによるword並列集合演算、event・値順のオフライン走査
- ABC366 G「XOR Neighbors」 公式問題主題: 線形方程式・rank
技能・出典
主題: 線形方程式・rank(制約を体上の連立一次方程式へ写し、Gaussian eliminationでrank・可解性・解空間次元を求める。その発動条件、正当性、計算量を説明し、未知問へ実装できる。)。既習技能: bitsetで集合演算をword並列化する(集合をbit列へ符号化し、交差・和・shift・popcountをword並列に実行した計算量を評価できる。) / 成立証明から構成解を復元する(成立証明に対応する親・局所操作・選択を記録し、要件を満たす構成を出力できる。)。主タグ: 線形方程式・rank / 補助タグ: bitsetによるword並列集合演算、構成解・witness復元
- ABC430 G「Range Set Modifying Query」 公式問題
技能・出典
主題: Segment Tree Beats(nodeの最大/次点/個数等からrange chmin/chmaxが一括適用できる条件を判定し、失敗時だけ子へ降りる。その発動条件、正当性、計算量を説明し、未知問へ実装できる。)。既習技能: bitsetで集合演算をword並列化する(集合をbit列へ符号化し、交差・和・shift・popcountをword並列に実行した計算量を評価できる。) / 単調進行による償却解析(要素の一方向移動・一度だけの削除・軽辺へ進むたびの部分問題サイズ半減など、単調に減るpotentialから操作列全体の仕事量を抑えられる。)。主タグ: Segment Tree Beats / 補助タグ: 単調進行による償却解析、bitsetによるword並列集合演算
前提・学習成果・出典
習得対象の目安: 水色(1200–1599)。真偽配列の演算をbit演算へ写し、word幅を含めた計算量を見積もる。
対象色の読み方は本書の読み方を参照してください。
概念上の親: データ構造と問い合わせ。問題へ進む前に、下記の直接前提のうち未習得の単元を確認する。
Canonical taxonomy: FinalTaxonomyBuild final-taxonomy-build-initial digest f1ae39bc7201c3374c108e800284e1e0068ce6f7a57f15b2a9e5219616e3c4fe / LearningUnit unit-bitset-word-parallel
習得する技能
- 集合をbit列へ符号化し、交差・和・shift・popcountをword並列に実行した計算量を評価できる。
前提と範囲
共通前提: prereq-abc-advanced-v1 (1.0.0)。
直接の前提単元: なし。
このUnitを直接前提とする単元: なし。
集合の交差・和・shiftを機械語word単位で同時処理し、要素ごとの走査をword幅だけ短縮する。
このUnitでは扱わないもの
- 集合状態そのものを一つずつ遷移するbitmask DP、および単一整数のbit演算だけで完結する処理。