平方根・閾値による軽重分類
概要
頻度・次数・更新回数を閾値でheavy/lightに分け、両側の計算量を均衡させる。
考え方
大きさBを境に軽い対象は全走査、重い対象は前計算や専用状態で扱う。重い対象が総量N/B個以下になることを利用し、軽い側と重い側の費用を釣り合わせる。
例えば総出現数Mの値別listを、長さ>Bならheavy、それ以外lightに分ける。heavy値は高々M/B種類である。query対象がlightならそのlistを直接O(B)走査し、heavyなら前計算した要約を読む、とすればQ queryの軽い側はO(QB)。各heavy値について全N対象へ要約を作る前処理はO(NM/B)。合計O(QB+NM/B)なので、B≈√(NM/Q)を取り、有効な範囲へclampして釣り合わせる。
閾値√Nが常に最適とは限らず、更新回数・query回数とheavy一種類の費用で式を立ててから選ぶ。動的分類なら値が閾値をまたぐ再構築や、入力全体で固定したheavy集合の正当性も数える。list走査のコストとheavy種類数の上界は異なる側へ課金する。
成立条件と計算量
典型的なN B+N²/Bの式ならB≈√Nだが、query数や更新費用で最適な閾値は変わる。重い対象数の上界を証明し、再分類費用と空間も数える。平方根を機械的に代入しない。
問題一覧
- ABC335 F「Hop Sugoroku」 公式問題
技能・出典
主題: 平方根・閾値による軽重分類(頻度・次数・更新回数を閾値でheavy/lightに分け、両側の計算量を均衡させる。その発動条件、正当性、計算量を説明し、未知問へ実装できる。)。主タグ: 平方根・閾値による軽重分類
- ABC350 G「Mediator」 公式問題
技能・出典
主題: 平方根・閾値による軽重分類(頻度・次数・更新回数を閾値でheavy/lightに分け、両側の計算量を均衡させる。その発動条件、正当性、計算量を説明し、未知問へ実装できる。)。主タグ: 平方根・閾値による軽重分類
- ABC219 G「Propagation」 公式問題
技能・出典
主題: 平方根・閾値による軽重分類(頻度・次数・更新回数を閾値でheavy/lightに分け、両側の計算量を均衡させる。その発動条件、正当性、計算量を説明し、未知問へ実装できる。)。主タグ: 平方根・閾値による軽重分類
- ABC365 G「AtCoder Office」 公式問題
技能・出典
主題: 平方根・閾値による軽重分類(頻度・次数・更新回数を閾値でheavy/lightに分け、両側の計算量を均衡させる。その発動条件、正当性、計算量を説明し、未知問へ実装できる。)。既習技能: 尺取り法・sliding windowで連続区間を走査する(一列の窓または二列の現在blockに関する不変条件を保ち、各pointerを単調に進められる。)。主タグ: 平方根・閾値による軽重分類 / 補助タグ: 尺取り法・sliding window
- ABC259 Ex「Yet Another Path Counting」 公式問題
技能・出典
主題: 平方根・閾値による軽重分類(頻度・次数・更新回数を閾値でheavy/lightに分け、両側の計算量を均衡させる。その発動条件、正当性、計算量を説明し、未知問へ実装できる。)。既習技能: グリッド・多次元表の局所DPを設計する(グリッドまたは多次元表の依存方向と境界状態を定め、計算済みの局所近傍からDAG順に全状態を更新できる。) / 組合せ係数と対称性で数える(選択・順列・分配の重複の有無を識別し、組合せ係数の式を立てられる。)。主タグ: 平方根・閾値による軽重分類 / 補助タグ: 組合せ係数・数え上げ、グリッド・多次元表の局所DP
各問題の解説は問題ごとの本文として執筆します。各項目には主題・追加で学ぶ技能・既習技能の役割を示します。
関連問題
他の主題と組み合わせる問題を読む
以下はこのUnitのOutcomeを追加で学ぶ技能または既習技能として参照する、別のUnitを主題とする問題です。
- ABC345 G「Sugoroku 5」 公式問題主題: 組合せを生成関数へ符号化する
技能・出典
主題: 組合せを生成関数へ符号化する(組合せの合成を生成関数の積・逆数・畳み込みに符号化できる。)。追加で学ぶ技能: NTT・FFTで畳み込みと相互相関を求める(係数積和または反転列との相互相関を多項式積へ変換し、NTT・FFTで必要な係数範囲を計算できる。)。既習技能: 平方根・閾値による軽重分類(頻度・次数・更新回数を閾値でheavy/lightに分け、両側の計算量を均衡させる。その発動条件、正当性、計算量を説明し、未知問へ実装できる。) / 法上の四則演算・高速累乗・逆元(剰余を正規化して加減乗算し、二分累乗と可逆性を確認した逆元により法上の除算・確率を計算できる。) / 再帰分割・分割統治(pivot・上位bit・短い側で部分問題へ再帰分割するか、部分結果をbalancedな積木・remainder tree・CDQで重複なく合成できる。) / 組合せ係数と対称性で数える(選択・順列・分配の重複の有無を識別し、組合せ係数の式を立てられる。)。主タグ: 畳み込み・相互相関、生成関数による組合せ構造の符号化 / 補助タグ: 組合せ係数・数え上げ、法上の四則演算・高速累乗・逆元、再帰分割・分割統治、平方根・閾値による軽重分類
前提・学習成果・出典
習得対象の目安: 青色(1600–1999)。頻度や次数で場合分けし、二つの計算量の釣合いから閾値を選ぶ。
対象色の読み方は本書の読み方を参照してください。
概念上の親: 軽重分類と償却解析で総仕事量を抑える。問題へ進む前に、下記の直接前提のうち未習得の単元を確認する。
Canonical taxonomy: FinalTaxonomyBuild final-taxonomy-build-initial digest f1ae39bc7201c3374c108e800284e1e0068ce6f7a57f15b2a9e5219616e3c4fe / LearningUnit unit-threshold-heavy-light
平方根・閾値による軽重分類
習得する技能
- 頻度・次数・更新回数を閾値でheavy/lightに分け、両側の計算量を均衡させる。その発動条件、正当性、計算量を説明し、未知問へ実装できる。
前提と範囲
共通前提: prereq-abc-advanced-v1 (1.0.0)。
直接の前提単元: なし。
このUnitを直接前提とする単元: なし。
頻度・次数・更新回数を閾値でheavy/lightに分け、両側の計算量を均衡させる。その発動条件と正当化原理を比較可能な独立教材として学ぶ。
このUnitでは扱わないもの
- 平方根・閾値による軽重分類の発動条件・不変量を使わず、実装部品だけを偶然共有する解法。