parallel binary search・多数境界の判定共有
概要
多数queryの未知境界をmidごとにbucketし、更新を一方向に進める判定器を各roundで共有する。
考え方
多数のqueryが同じ時系列上の単調な成立時点を探すなら、各queryの中点をbucketへ集める。一回の時系列再生でその段の全中点を判定し、探索区間を同時に半分へ縮める。
最初に成立する時点を探す場合、時点0は初期状態、Tは最後の更新後とし、queryごとに不成立側lo=−1、成立側hi=T+1(範囲外の番兵)を持つ。hi−lo>1のqueryをmid=floor((lo+hi)/2)のbucketへ置く。一roundでは構造を初期化し、時点0から更新を一度ずつ再生してbucket[t]を判定する。成立ならhi=t、不成立ならlo=t。全区間が隣接したらhiが最小成立時点、T+1なら一度も成立しない。番兵の状態を実際に再生・判定する必要はない。
成立条件と計算量
時点数T、query数Q、再生費用R、判定一回CならO((R+QC) log(T+2))。段ごとに状態を初期化し、未成立の番兵時点を用意する。判定状態を共有する方法であり、CPU並列処理を必須としない。
問題一覧
- ABC394 G「Dense Buildings」 公式問題
技能・出典
主題: parallel binary search・多数境界の判定共有(各queryの未確定区間を保ち、同じroundのmidをbucketして一方向更新できる判定器を共有し、全queryの最小・最大成立境界を求められる。)。既習技能: event順にactive集合を更新する(値・時刻・座標順にeventを並べ、同値eventの処理順とactive集合の増分更新を設計できる。) / DSUによる連結成分管理・縮約(静的な辺を探索して成分を付けるか、辺追加ごとに成分を併合し、同一成分・サイズを判定できる。) / 単調境界を証明して探索する(判定の単調性を証明し、二分探索の成功側・失敗側を設定できる。)。主タグ: parallel binary search・多数境界の判定共有 / 補助タグ: DSUによる連結成分管理・縮約、event・値順のオフライン走査、単調境界探索
- ABC233 Ex「Manhattan Christmas Tree」 公式問題
技能・出典
主題: parallel binary search・多数境界の判定共有(各queryの未確定区間を保ち、同じroundのmidをbucketして一方向更新できる判定器を共有し、全queryの最小・最大成立境界を求められる。)。既習技能: event順にactive集合を更新する(値・時刻・座標順にeventを並べ、同値eventの処理順とactive集合の増分更新を設計できる。) / 一次元・二次元累積和と差分で区間情報を線形化する(prefix配列またはprefix変数を置き、区間和を二つのprefix値の差で表現できる。多次元の直方体は2^D隅の包除で取得し、一括加算は端点差分へ変換できる。) / 反転数・重み付き接頭辞統計をFenwick Treeで保つ(処理済み値の頻度から反転数を数えるか、必要な添字付き接頭辞統計を導き、Fenwick Treeの線形結合で式を評価できる。) / 幾何の基本判定と座標変換(幾何条件を外積・距離式・端点順・格子占有・変換後座標の局所判定へ落とし込める。)。主タグ: parallel binary search・多数境界の判定共有 / 補助タグ: event・値順のオフライン走査、Fenwick Tree・反転数・重み付き接頭辞統計、幾何の基本判定・配置・座標変換、累積和・差分配列
各問題の解説は問題ごとの本文として執筆します。各項目には主題・追加で学ぶ技能・既習技能の役割を示します。
前提・学習成果・出典
習得対象の目安: 青色(1600–1999)。offline処理と二分探索を組み合わせ、複数queryで判定器の走査を共有する。
対象色の読み方は本書の読み方を参照してください。
概念上の親: モデル変換とアルゴリズム設計。問題へ進む前に、下記の直接前提のうち未習得の単元を確認する。
Canonical taxonomy: FinalTaxonomyBuild final-taxonomy-build-initial digest f1ae39bc7201c3374c108e800284e1e0068ce6f7a57f15b2a9e5219616e3c4fe / LearningUnit unit-parallel-binary-search
parallel binary search・多数境界の判定共有
習得する技能
- 各queryの未確定区間を保ち、同じroundのmidをbucketして一方向更新できる判定器を共有し、全queryの最小・最大成立境界を求められる。
前提と範囲
共通前提: prereq-abc-advanced-v1 (1.0.0)。
直接の前提単元: 単調境界を証明して探索する。
このUnitを直接前提とする単元: なし。
単一queryの単調境界を二分探索できるようになった後、多数queryのmidをroundごとに束ね、一方向更新できる判定器を共有する。
このUnitでは扱わないもの
- parallel binary search・多数境界の判定共有の発動条件・不変量を使わず、実装部品だけを偶然共有する解法。