ABC 296 E — Transition Game

考察

写像f(i)=A_iの反復像S_0⊇S_1⊇…の安定集合はfunctional graphの閉路頂点だけになる。削除された頂点xは唯一の出辺先A_xの有効入次数を一つ減らし、新たに0なら同様に消える。

採用する候補: 入次数0からのleaf pruning

閉路外頂点をqueueで順に削れば残る頂点数が無限反復後にも選べる数と一致する。

棄却する候補: ゲーム回数ごとに集合像を再構成

安定まで最大N回、各回N走査で二次になる。

全入次数を数え、0の頂点をqueueへ入れて取り出すたびA_xの入次数を減らす。削除されなかった頂点数を答える。

典型の発動条件

functional graphの閉路抽出

発動条件: 各頂点の出次数が1で、反復後に残る頂点を求める。

入次数0から木部分を剥がす。

問題固有の要素

ゲームの全時刻条件を写像の安定像へ変えると、functional graphのcycle membershipになる。

別の問題へ持ち帰る視点: 有限写像の無限反復像は閉路集合である。

正当性

写像像を繰り返すと先行点を持たない木頂点から順に失われる。一方cycle頂点はcycle内先行点を常に持ち像に残る。入次数peelingの未削除点はこの安定集合と一致する。

実装上の注意

  • 自己loopも閉路として残し、削除済み数または残数を一度だけ更新する。

復習の核

  • 直接集合反復と比較し、自己loop、複数cycle、長いtailを確認する。

計算量と制約

時間

N 頂点に対して O(N)。

空間

入次数、出辺とqueue O(N)。

制約との対応

公式制約の確認範囲: Time limit: 2 sec; Memory limit: 1024 MiB; Constraints: 1\leq N\leq 2\times 10^5; 1\leq A_i\leq N; All values in the input are integers.

出典

分類・前提・執筆情報

掲載状態: 収録済み

Transition Game の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

主題の単元: 関数グラフのcycle・tree分解

主題
追加で学ぶ技能
    なし
    既習技能
      なし

      主タグ: 関数グラフのcycle・tree分解

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

      学習の位置

      体系上の位置: 関数グラフのcycle・tree分解

      • 後続が一意なグラフをcycleと流入木へ分け、各頂点が属する構造を特定できる。

      先に読む単元:

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

      学習記録

      状況更新: 更新記録なし

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

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

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

      同じ単元の問題