doubling・binary lifting
決定的遷移の2^k回後と累積値を合成し、巨大回数のjumpを二進分解で求める。
この典型を扱う単元: doubling・binary lifting
検索別名: binary lifting、doubling、ダブリング
未知問からこの典型を見つける手掛かり
- 扱う対象
- ancestor
- 写像
- 決定的遷移
- 使う手掛かり
- K回後
- jump
- 巨大回数
- 保つ不変量
- 2冪合成
- 結合順
- 求めるもの
- 累積遷移
- 高速jump
- 適用しない条件
- 個別の除外条件の記載はありません。扱う対象と使う手掛かりから適用を判断してください。
分類・前提・学習成果
分類と直接の前提
概念上の親: グラフモデルと構造
関連する典型
- monoid exponentiation・連結演算doubling: 2冪長の遷移を前計算し、指数のbit分解で必要な合成だけを選ぶ構造が共通する。
学習成果と学習単位
一意な遷移の2の冪回先を前計算し、巨大回数後の状態または区間到達を求められる。
doubling・binary liftingで学ぶ
代表問題
この典型の考え方を具体的な問題で確かめるための入口です。
関連問題
この典型が主タグまたは補助タグとして付いている問題です。
- ABC212 F「Greedy Takahashi」 公式問題主題: doubling・binary lifting / 主タグ
- ABC254 G「Elevators」 公式問題主題: doubling・binary lifting / 主タグ
- ABC310 G「Takahashi And Pass-The-Ball Game」 公式問題主題: doubling・binary lifting / 主タグ
- ABC367 E「Permute K times」 公式問題主題: doubling・binary lifting / 主タグ
- ABC370 F「Cake Division」 公式問題主題: 尺取り法・sliding windowで連続区間を走査する / 補助タグ
技能・出典
主題: 尺取り法・sliding windowで連続区間を走査する
主タグ: 尺取り法・sliding window / 補助タグ: doubling・binary lifting、単調境界探索
- ABC417 G「Binary Cat」 公式問題主題: 圧縮・反復・再帰文字列へ問い合わせる / 補助タグ
- ABC438 E「Heavy Buckets」 公式問題主題: doubling・binary lifting / 主タグ