状態グラフのモデリングと探索
暗黙状態と重みなし合法遷移を頂点・辺へ写し、探索目的・訪問条件・frontierに応じてBFS・DFS・backtrackingを選ぶ。
この典型を扱う単元: 状態グラフのモデリングと探索
検索別名: implicit graph search、状態グラフ、状態空間探索
未知問からこの典型を見つける手掛かり
- 扱う対象
- グリッド
- 状態
- 遷移
- 使う手掛かり
- 到達可能
- 暗黙graph
- 最小手数
- 保つ不変量
- visited
- 探索frontier
- 求めるもの
- 到達判定
- 最短手数
- 適用しない条件
- 個別の除外条件の記載はありません。扱う対象と使う手掛かりから適用を判断してください。
分類・前提・学習成果
分類と直接の前提
概念上の親: グラフモデルと構造
関連する典型
- 最短路モデル: 問題状態を頂点、合法操作を辺へ写してから、辺重みに応じた最短路algorithmを選ぶ流れで併用する。
学習成果と学習単位
暗黙状態・重みなし辺・訪問条件を定義し、到達判定・最短手数・列挙の目的に応じてBFS・DFS・backtrackingを選べる。
状態グラフのモデリングと探索で学ぶ
代表問題
この典型の考え方を具体的な問題で確かめるための入口です。
- ABC302 F「Merge Set」 公式問題主題: 状態グラフのモデリングと探索 / 主タグ
- ABC427 E「Wind Cleaning」 公式問題主題: 状態グラフのモデリングと探索 / 主タグ
関連問題
この典型が主タグまたは補助タグとして付いている問題です。
- ABC241 F「Skate」 公式問題主題: 状態グラフのモデリングと探索 / 主タグ
- ABC244 F「Shortest Good Path」 公式問題主題: 状態グラフのモデリングと探索 / 主タグ
- ABC257 G「Prefix Concatenation」 公式問題主題: Z algorithmによるprefix matching / 補助タグ
- ABC289 E「Swap Places」 公式問題主題: 状態グラフのモデリングと探索 / 主タグ
- ABC302 F「Merge Set」 公式問題主題: 状態グラフのモデリングと探索 / 主タグ
- ABC305 F「Dungeon Explore」 公式問題主題: 状態グラフのモデリングと探索 / 主タグ
- ABC317 E「Avoid Eye Contact」 公式問題主題: 方向別grid scanによる長距離効果の前計算 / 補助タグ
- ABC319 G「Counting Shortest Paths」 公式問題主題: 状態グラフのモデリングと探索 / 主タグ
技能・出典
主題: 状態グラフのモデリングと探索
主タグ: 状態グラフのモデリングと探索 / 補助タグ: 単調進行による償却解析、DP遷移の集約・高速化、ordered set・multisetの動的順序管理
- ABC336 F「Rotation Puzzle」 公式問題主題: meet-in-the-middle・半分全列挙 / 補助タグ
- ABC355 E「Guess the Sum」 公式問題主題: 状態グラフのモデリングと探索 / 主タグ
- ABC361 G「Go Territory」 公式問題主題: 状態グラフのモデリングと探索 / 主タグ
- ABC394 E「Palindromic Shortest Path」 公式問題主題: 状態グラフのモデリングと探索 / 主タグ
- ABC413 F「No Passage」 公式問題主題: 循環局面の後退解析とminimax距離 / 補助タグ
- ABC414 F「Jump Traveling」 公式問題主題: 状態グラフのモデリングと探索 / 主タグ
- ABC417 E「A Path in A Dictionary」 公式問題主題: 交換論から選択順を導く / 補助タグ
- ABC427 E「Wind Cleaning」 公式問題主題: 状態グラフのモデリングと探索 / 主タグ
- ABC429 E「Hit and Away」 公式問題主題: 状態グラフのモデリングと探索 / 主タグ
- ABC443 F「Non-Increasing Number」 公式問題主題: 状態グラフのモデリングと探索 / 主タグ
- ABC446 E「Multiple-Free Sequences」 公式問題主題: 状態グラフのモデリングと探索 / 主タグ
- ABC446 F「Reachable Set 2」 公式問題主題: 状態グラフのモデリングと探索 / 主タグ