ABC 291 E — Find Permutation

考察

大小制約X_i<Y_iは有向辺X_i→Y_iとみなせ、条件を満たす順列はこのDAGのトポロジカル順序と一対一に対応する。ある段階で入次数0が二頂点以上ならどちらを先にしても順序が作れ、常に一頂点なら選択の余地がない。

採用する候補: Kahn法で各段階の入次数0頂点が一つか検査

トポロジカル順序が一意である必要十分条件を探索中の候補数として直接判定し、その順序から各値を復元できる。

棄却する候補: 任意のトポロジカル順序を一つ求める

一解の存在は保証されるが、別順序の有無を判定できない。

入次数0集合を用いるKahn法を行い、各段階で候補がちょうど一つか確認しながら順序Pを作り、A[P_i]=iを出力する。

典型の発動条件

一意なトポロジカルソート

発動条件: DAGの線形拡張が一意かを知りたい。

入次数0集合のサイズを毎段階確認する。

順序から順位への逆写像

発動条件: 頂点列Pが大小順位を表す。

A[P_i]=iとして要求順列を構成する。

問題固有の要素

順列制約の一意性を値の推測でなくDAGの線形拡張一意性へ置き換える。

別の問題へ持ち帰る視点: 全順序制約はDAG化し、Kahn法の選択肢数で一意性を調べる。

正当性

各段の入次数0は次に置ける要素。二候補ならどちら先でも残りのtopological orderを完成でき順序非一意。全段一候補なら選択が強制され一意。取り出し数N未満ならcycleで順序が存在しない。得た順序の逆対応が要求順位列。

実装上の注意

  • 候補集合サイズは取り出す直前に判定し、得た頂点順とAへの逆写像を混同しない。

復習の核

  • 小DAGの全トポロジカル順列と比較し、途中だけ候補が二つになる例と完全鎖を確認する。

計算量と制約

時間

N 頂点、M 制約。Kahn法 O(N+M)。

空間

隣接、入次数、queueと順列 O(N+M)。

制約との対応

公式制約の確認範囲: Time limit: 2 sec; Memory limit: 1024 MiB; Constraints: 2 \leq N \leq 2\times 10^5; 1 \leq M \leq 2\times 10^5; 1\leq X_i,Y_i \leq N; All values in the input are integers.; There is an A consistent with the input.

出典

分類・前提・執筆情報

掲載状態: 収録済み

Find Permutation の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

主題の単元: DAGのtopological processing

主題
  • DAGのtopological processing: 依存辺の向きを定め、入次数またはpostorderからtopological順を作って制約伝播・DP・scheduleを処理する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。
追加で学ぶ技能
    なし
    既習技能
      なし

      主タグ: DAGのtopological processing

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

      学習の位置

      体系上の位置: DAGのtopological processing

      • 依存辺の向きを定め、入次数またはpostorderからtopological順を作って制約伝播・DP・scheduleを処理する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。

      先に読む単元:

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

      学習記録

      状況更新: 更新記録なし

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

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

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

      同じ単元の問題