単調進行による償却解析
要素の一方向移動・一度だけの削除・軽辺へ進むたびの部分問題サイズ半減など、単調に減るpotentialから操作列全体の仕事量を抑える。
この典型を扱う単元: 単調進行による償却解析
検索別名: amortized analysis、light-edge size halving、potential method、償却解析、軽辺サイズ半減
未知問からこの典型を見つける手掛かり
- 扱う対象
- 候補
- 操作列
- 要素
- 使う手掛かり
- light edge
- size halving
- 一度だけ
- 単調に減る
- 移動回数
- 部分問題サイズ半減
- 保つ不変量
- potential
- 総削除回数
- 軽辺遷移ごとのサイズ半減
- 求めるもの
- 償却上界
- 総計算量
- 適用しない条件
- 個別の除外条件の記載はありません。扱う対象と使う手掛かりから適用を判断してください。
分類・前提・学習成果
分類と直接の前提
概念上の親: モデル変換
関連する典型
学習成果と学習単位
要素の一方向移動・一度だけの削除・軽辺へ進むたびの部分問題サイズ半減など、単調に減るpotentialから操作列全体の仕事量を抑えられる。
単調進行による償却解析で学ぶ
代表問題
この典型の考え方を具体的な問題で確かめるための入口です。
- ABC217 E「Sorting Queries」 公式問題主題: 単調進行による償却解析 / 主タグ
- ABC256 Ex「I like Query Problem」 公式問題主題: 単調進行による償却解析 / 主タグ
- ABC267 E「Erasing Vertices 2」 公式問題主題: 単調境界を証明して探索する / 補助タグ
- ABC329 E「Stamp」 公式問題主題: 時間を逆向きにして未来依存を消す / 補助タグ
- ABC417 G「Binary Cat」 公式問題主題: 圧縮・反復・再帰文字列へ問い合わせる / 補助タグ
関連問題
この典型が主タグまたは補助タグとして付いている問題です。
- ABC217 E「Sorting Queries」 公式問題主題: 単調進行による償却解析 / 主タグ
- ABC255 Ex「Range Harvest Query」 公式問題主題: 端点更新型のrun分割管理 / 補助タグ
- ABC256 Ex「I like Query Problem」 公式問題主題: 単調進行による償却解析 / 主タグ
- ABC267 E「Erasing Vertices 2」 公式問題主題: 単調境界を証明して探索する / 補助タグ
- ABC282 Ex「Min + Sum」 公式問題主題: 再帰分割・分割統治 / 補助タグ
- ABC295 G「Minimum Reachable City」 公式問題主題: 単調path contraction・DSU jump / 補助タグ
技能・出典
主題: 単調path contraction・DSU jump
主タグ: 単調path contraction・DSU jump / 補助タグ: 単調進行による償却解析、DSUによる連結成分管理・縮約
- ABC302 E「Isolation」 公式問題主題: 単調進行による償却解析 / 主タグ
- ABC305 F「Dungeon Explore」 公式問題主題: 状態グラフのモデリングと探索 / 補助タグ
- ABC307 F「Virus 2」 公式問題主題: 最短路モデル / 補助タグ
- ABC312 Ex「snukesnuke」 公式問題主題: 文字列周期・primitive word / 補助タグ
技能・出典
主タグ: 文字列周期・primitive word / 補助タグ: 単調進行による償却解析、Z algorithmによるprefix matching
- ABC319 G「Counting Shortest Paths」 公式問題主題: 状態グラフのモデリングと探索 / 補助タグ
技能・出典
主題: 状態グラフのモデリングと探索
主タグ: 状態グラフのモデリングと探索 / 補助タグ: 単調進行による償却解析、DP遷移の集約・高速化、ordered set・multisetの動的順序管理
- ABC329 E「Stamp」 公式問題主題: 時間を逆向きにして未来依存を消す / 補助タグ
- ABC364 F「Range Connect MST」 公式問題主題: cut・cycle性質から最適全域木を構成する / 補助タグ
技能・出典
主タグ: 最小・最大全域木とcut・cycle性質 / 補助タグ: 単調進行による償却解析、DSUによる連結成分管理・縮約、ordered set・multisetの動的順序管理
- ABC368 G「Add and Multiply Queries」 公式問題主題: 単調進行による償却解析 / 主タグ
- ABC403 E「Forbidden Prefix」 公式問題主題: 単調進行による償却解析 / 主タグ
- ABC417 G「Binary Cat」 公式問題主題: 圧縮・反復・再帰文字列へ問い合わせる / 補助タグ
- ABC421 F「Erase between X and Y」 公式問題主題: 要素索引と連結リストで局所linkを更新する / 補助タグ
- ABC426 F「Clearance」 公式問題主題: 区間更新を要約へ作用させる / 補助タグ
- ABC427 G「Takahashi's Expectation 2」 公式問題主題: 同値な状態を正規化する / 補助タグ
- ABC428 F「Pyramid Alignment」 公式問題主題: 単調進行による償却解析 / 主タグ
- ABC430 G「Range Set Modifying Query」 公式問題主題: Segment Tree Beats / 補助タグ
- ABC435 E「Cover query」 公式問題主題: 端点更新型のrun分割管理 / 補助タグ
- ABC466 F「Many Mod Calculation」 公式問題主題: 単調進行による償却解析 / 主タグ