rollback・DFS入退場の状態復元
更新前の差分をstackへ記録し、分割統治・時間Segment Tree・DFSの退場時に状態を正確に巻き戻す。
この典型を扱う単元: rollback・DFS入退場の状態復元
検索別名: rollback DSU、undo stack、ロールバックデータ構造
未知問からこの典型を見つける手掛かり
- 扱う対象
- DFS path
- snapshot
- 変更履歴
- 使う手掛かり
- offline dynamic
- 分岐探索
- 退場時に戻す
- 保つ不変量
- stack height
- 変更差分
- 求めるもの
- 時間分割
- 状態復元
- 適用しない条件
- 個別の除外条件の記載はありません。扱う対象と使う手掛かりから適用を判断してください。
分類・前提・学習成果
分類と直接の前提
概念上の親: 更新可能な最小十分要約
関連する典型
- backtracking・可逆な探索状態: 再帰へ入る前の更新と復帰時のundoを対にし、現在pathだけの不変条件を保つ設計が共通する。
- 永続data structure・structural sharing: 過去版を共有して保持する永続化と、現在状態をundoして探索順に戻すrollbackを区別する。
学習成果と学習単位
更新前の差分をstackへ記録し、分割統治・時間Segment Tree・DFSの退場時に状態を正確に巻き戻す。その発動条件、正当性、計算量を説明し、未知問へ実装できる。
rollback・DFS入退場の状態復元で学ぶ
代表問題
この典型の考え方を具体的な問題で確かめるための入口です。
関連問題
この典型が主タグまたは補助タグとして付いている問題です。
- ABC218 G「Game on Tree 2」 公式問題主題: rollback・DFS入退場の状態復元 / 主タグ
技能・出典
主タグ: rollback・DFS入退場の状態復元 / 補助タグ: 有限局面DAGのminimax、ordered set・multisetの動的順序管理
- ABC302 Ex「Ball Collector」 公式問題主題: rollback・DFS入退場の状態復元 / 主タグ
- ABC363 G「Dynamic Scheduling」 公式問題主題: rollback・DFS入退場の状態復元 / 主タグ
技能・出典
主タグ: rollback・DFS入退場の状態復元 / 補助タグ: 二部matching・Hall・Kőnig、遅延評価する区間作用、Segment Treeのcanonical区間分解