ABC 291 F — Teleporter and Closed off

考察

都市番号は常に増え、一度kを避ける経路は必ずi<k<jとなる一本のテレポーターでkを飛び越す。辺長が高々M≤10なので、kを跨ぐ辺候補はO(M^2)個しかなく、全kでも十分小さい。

採用する候補: 前後最短DPとkを跨ぐ辺の列挙

1→iとj→Nの最短回数を共通前計算し、辺i→jを中央に置く候補だけを各kで比較すればよい。

棄却する候補: kごとにグラフから頂点を消して最短路

N回の探索が必要で、同じ前後経路を再計算してしまう。

dp0[i]とdp1[i]を前後から計算し、各kについて存在するi→jでi<k<jかつj-i≤Mを列挙してdp0[i]+1+dp1[j]の最小を取る。

典型の発動条件

DAG最短路DP

発動条件: 全辺が小さい番号から大きい番号へ向く。

前向きdp0と後ろ向きdp1を番号順に計算する。

障害点を跨ぐ境界分解

発動条件: 単調路から一頂点を除く。

除去頂点の左から右へ直接飛ぶ一辺を境に前後最短路を結合する。

問題固有の要素

避ける頂点ごとの経路全体ではなく、その頂点を跨ぐ唯一の辺だけを列挙すればよい。

別の問題へ持ち帰る視点: 単調DAGの一点回避は境界横断辺で前後DPを接合する。

正当性

番号増加pathがkを避けると一意の辺i→jでi<k<jを跨ぐ。その前後はkを訪れられない番号域なので元の最短prefix/suffixを独立に使える。全crossing辺の最小が漏れなく最短避難pathを与える。

実装上の注意

  • 到達不能INFを含む和を除外し、i<k<jとj-i≤Mの添字境界を守る。

復習の核

  • 小さいDAGで頂点削除BFSと照合し、飛越辺なし、複数候補同値、M=1に近い境界を確認する。

計算量と制約

時間

都市N、最大jumpM。前後DP O(NM)、各禁止都市で crossing候補 O(M²)、全体 O(NM²)。

空間

入力 O(NM)、前後DP O(N)。

制約との対応

公式制約の確認範囲: Time limit: 2 sec; Memory limit: 1024 MiB; Constraints: 3 \leq N \leq 10^5; 1\leq M\leq 10; M<N; S_i is a string of length M consisting of 0 and 1.; If i+j>N, then the j-th character of S_i is 0.; N and M are integers.

出典

分類・前提・執筆情報

掲載状態: 収録済み

Teleporter and Closed off の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

主題の単元: 最短路モデル

主題
  • 最短路モデル: DAGや使用可能な辺列の順に緩和し、処理済みprefixが表す経路集合を不変量として説明できる。
追加で学ぶ技能
    なし
    既習技能
      なし

      主タグ: 最短路モデル

      執筆: abc-explanation-author1.1.1 / revision 2

      学習の位置

      体系上の位置: 最短路モデル

      • DAGや使用可能な辺列の順に緩和し、処理済みprefixが表す経路集合を不変量として説明できる。

      先に読む単元:

      • 状態グラフのモデリングと探索 — 暗黙状態と重みなし合法遷移を頂点・辺へ写し、探索目的・訪問条件・frontierに応じてBFS・DFS・backtrackingを選ぶ。その発動条件と正当化原理を比較可能な独立教材として学ぶ。

      学習記録

      状況更新: 更新記録なし

      復習設定更新: 更新記録なし

      端末内の保存状態を確認しています。

      要復習一覧 / 学習記録のバックアップ / 解説に戻る

      同じ単元の問題