ABC 429 F — Shortest Path Query
分類・前提・執筆情報
掲載状態: 収録済み
Shortest Path Query の公式問題ページ(外部リンク)
最終確認:
学習上の位置付け
主題の単元: 区間monoid要約
- 主題
- 区間monoid要約: 要約する値・単位元・結合的な合成規則を定義し、prefix fold・Segment Tree・SWAGで答えを求められる。
- 追加で学ぶ技能
- 既習技能
- 半環行列・min-plus/max-min遷移: 遷移を半環行列として定義し、結合則と単位元を保つ二分累乗・区間積で巨大回数の最適化遷移を計算できる。
- 最短路モデル: DAGや使用可能な辺列の順に緩和し、処理済みprefixが表す経路集合を不変量として説明できる。
主タグ: 区間monoid要約
執筆: abc-explanation-author1.1.1 / revision 3
学習の位置
体系上の位置: 区間monoid要約
- 要約する値・単位元・結合的な合成規則を定義し、prefix fold・Segment Tree・SWAGで答えを求められる。
先に読む単元:
- 半環行列・min-plus/max-min遷移 — 線形遷移・行列累乗で得た考え方と実装を再利用し、半環行列・min-plus/max-min遷移の発動条件・正当化・境界を重複なく学ぶ。
- 最短路モデル — 基本的な明示グラフ探索を土台に、辺重みに応じた緩和・距離確定順を選び、最短距離と計算量を求める。
学習記録
状況更新: 更新記録なし
復習設定更新: 更新記録なし
端末内の保存状態を確認しています。
要復習一覧 / 学習記録のバックアップ / 解説に戻る
同じ単元の問題
- ABC432-E — Clamp
- ABC343-F — Second Largest Query
- ABC223-F — Parenthesis Checking
- ABC415-F — Max Combo
- ABC424-F — Adding Chords
- ABC331-F — Palindrome Query
- ABC285-F — Substring of Sorted String
- ABC460-F — Farthest Pair Query
- ABC440-F — Egoism
- ABC292-EX — Rating Estimator
- ABC447-G — Div. 1 & Div. 2
- ABC418-F — We're teapots
- ABC365-F — Takahashi on Grid
- ABC246-EX — 01? Queries
- ABC434-G — Keyboard