基準解による変更影響の局所化
変更前の解・実行列をwitnessとし、それを壊さない変更では答えが変わらないと示して再計算対象を絞る。
この典型を扱う単元: 基準witnessから変更影響を局所化する
検索別名: replacement paths、witness-based sensitivity analysis、変更影響の局所化
未知問からこの典型を見つける手掛かり
- 扱う対象
- witness
- 削除
- 基準解
- 変更
- 実行列
- 使う手掛かり
- 一箇所変更
- 再計算
- 各操作を除く
- 保つ不変量
- witnessが壊れない
- 基準解に含まれない
- 答えは変わらない
- 求めるもの
- 各削除
- 変更後の答え
- 影響範囲
- 適用しない条件
- 個別の除外条件の記載はありません。扱う対象と使う手掛かりから適用を判断してください。
分類・前提・学習成果
分類と直接の前提
概念上の親: モデル変換
関連する典型
学習成果と学習単位
基準となる解や経路を証拠に、答えが変わり得る変更だけを特定して再計算を局所化できる。
基準witnessから変更影響を局所化するで学ぶ
代表問題
この典型の考え方を具体的な問題で確かめるための入口です。
関連問題
この典型が主タグまたは補助タグとして付いている問題です。
- ABC218 F「Blocked Roads」 公式問題主題: 基準witnessから変更影響を局所化する / 主タグ
- ABC243 E「Edge Deletion」 公式問題主題: 最短路モデル / 補助タグ
- ABC279 E「Cheating Amidakuji」 公式問題主題: 基準witnessから変更影響を局所化する / 主タグ
- ABC448 G「Conquest」 公式問題主題: Convex Hull Trick・直線包絡 / 補助タグ