再帰分割・分割統治
pivot・bit・時刻区間・積木で部分問題へ再帰分割し、部分結果を重複なく合成する。
この典型を扱う単元: 再帰分割・分割統治
検索別名: CDQ分割統治、divide and conquer、分割統治
未知問からこの典型を見つける手掛かり
- 扱う対象
- pivot
- 再帰木
- 区間
- 使う手掛かり
- pivot
- 中央
- 左右へ分割
- 保つ不変量
- 一意な部分問題
- 因果順
- 求めるもの
- 再帰合成
- 重複削減
- 適用しない条件
- 個別の除外条件の記載はありません。扱う対象と使う手掛かりから適用を判断してください。
分類・前提・学習成果
分類と直接の前提
概念上の親: モデル変換
関連する典型
学習成果と学習単位
pivot・上位bit・短い側で部分問題へ再帰分割するか、部分結果をbalancedな積木・remainder tree・CDQで重複なく合成できる。
再帰分割・分割統治で学ぶ
代表問題
この典型の考え方を具体的な問題で確かめるための入口です。
- ABC282 Ex「Min + Sum」 公式問題主題: 再帰分割・分割統治 / 主タグ
- ABC304 G「Max of Medians」 公式問題主題: XOR閾値matchingのbit分割再帰 / 補助タグ
関連問題
この典型が主タグまたは補助タグとして付いている問題です。
- ABC213 H「Stroll」 公式問題主題: Relaxed・online convolution / 補助タグ
- ABC230 H「Bullion」 公式問題主題: 母関数方程式・高度な係数抽出 / 補助タグ
- ABC247 Ex「Rearranging Problem」 公式問題主題: 組合せを生成関数へ符号化する / 補助タグ
- ABC260 Ex「Colorfulness」 公式問題主題: 組合せを生成関数へ符号化する / 補助タグ
技能・出典
主題: 組合せを生成関数へ符号化する
主タグ: 形式的べき級数の基本演算、生成関数による組合せ構造の符号化 / 補助タグ: 組合せ係数・数え上げ、畳み込み・相互相関、集合上の包除原理、法上の四則演算・高速累乗・逆元、再帰分割・分割統治
- ABC267 Ex「Odd Sum」 公式問題主題: 組合せを生成関数へ符号化する / 補助タグ
- ABC269 Ex「Antichain」 公式問題主題: heavy path上の多項式木DP / 補助タグ
技能・出典
主タグ: heavy path上の多項式木DP / 補助タグ: 畳み込み・相互相関、生成関数による組合せ構造の符号化、再帰分割・分割統治、根付き木DP・部分木集約
- ABC272 Ex「Flipping Coins 2」 公式問題主題: 多項式の多点評価・補間 / 補助タグ
技能・出典
主題: 多項式の多点評価・補間
主タグ: 生成関数による組合せ構造の符号化、多項式の多点評価・補間 / 補助タグ: 組合せ係数・数え上げ、畳み込み・相互相関、集合上の包除原理、再帰分割・分割統治
- ABC273 Ex「Inv(0,1)ving Insert(1,0)n」 公式問題主題: Stern–Brocot木の経路と祖先 / 補助タグ
技能・出典
主タグ: Stern–Brocot木の経路と祖先 / 補助タグ: ordered set・multisetの動的順序管理、再帰分割・分割統治、small-to-large・DSU on Tree
- ABC281 Ex「Alchemy」 公式問題主題: 組合せを生成関数へ符号化する / 補助タグ
- ABC282 Ex「Min + Sum」 公式問題主題: 再帰分割・分割統治 / 主タグ
- ABC304 G「Max of Medians」 公式問題主題: XOR閾値matchingのbit分割再帰 / 補助タグ
- ABC317 Ex「Walk」 公式問題主題: 組合せを生成関数へ符号化する / 補助タグ
- ABC331 G「Collect Them All」 公式問題主題: 包除・Möbius反転で重複を補正する / 補助タグ
技能・出典
主タグ: 生成関数による組合せ構造の符号化、集合上の包除原理 / 補助タグ: 畳み込み・相互相関、法上の四則演算・高速累乗・逆元、再帰分割・分割統治
- ABC345 G「Sugoroku 5」 公式問題主題: 組合せを生成関数へ符号化する / 補助タグ
技能・出典
主題: 組合せを生成関数へ符号化する
主タグ: 畳み込み・相互相関、生成関数による組合せ構造の符号化 / 補助タグ: 組合せ係数・数え上げ、法上の四則演算・高速累乗・逆元、再帰分割・分割統治、平方根・閾値による軽重分類
- ABC348 G「Max (Sum - Max)」 公式問題主題: Monge・monotone minima最適化 / 補助タグ
- ABC352 G「Socks 3」 公式問題主題: 組合せを生成関数へ符号化する / 補助タグ
技能・出典
主題: 組合せを生成関数へ符号化する
主タグ: 畳み込み・相互相関、生成関数による組合せ構造の符号化 / 補助タグ: 組合せ係数・数え上げ、寄与の数え上げと順序交換、法上の四則演算・高速累乗・逆元、再帰分割・分割統治
- ABC357 G「Stair-like Grid」 公式問題主題: 包除・Möbius反転で重複を補正する / 補助タグ
- ABC381 G「Fibonacci Product」 公式問題主題: 拡大有限体の表現と四則演算を構成する / 補助タグ
- ABC383 G「Bar Cover」 公式問題主題: 分離凸・凹の単調限界値選択 / 補助タグ
- ABC385 G「Counting Buildings」 公式問題主題: 組合せを生成関数へ符号化する / 補助タグ
- ABC413 E「Reverse 2^i」 公式問題主題: 再帰分割・分割統治 / 主タグ
- ABC425 G「Sum of Min of XOR」 公式問題主題: bit列をTrieで索引化する / 補助タグ
- ABC426 G「Range Knapsack Query」 公式問題主題: 再帰分割・分割統治 / 主タグ
- ABC439 G「Sugoroku 6」 公式問題主題: FPS合成・power projection / 補助タグ
技能・出典
主タグ: 形式的べき級数の基本演算、FPS合成・power projection、生成関数による組合せ構造の符号化 / 補助タグ: 畳み込み・相互相関、法上の四則演算・高速累乗・逆元、再帰分割・分割統治