ABC 302 F — Merge Set

考察

集合のmergeを続けて1とMを同居させるには、1を含む集合から、共通要素を介して集合を渡り歩き、Mを含む集合へ到達すればよい。集合同士の共通部分を直接調べる代わりに、要素も頂点にする。二部グラフで要素1から要素Mまでのpathは、要素→集合→要素を交互に進む。pathが使う集合数をrとすると、それらを一つへまとめる操作回数はr-1なので、辺距離dからd/2-1へ変換できる。

採用する候補: 集合頂点と要素頂点からなる二部グラフをBFSする

入力に現れる所属関係だけを辺にでき、集合の共有要素関係を明示的にO(N^2)列挙せず最短merge回数を得られる。

棄却する候補: 全ての集合pairの共通部分を調べて集合グラフを作る

集合pairがO(N^2)あり、所属総数が小さくても制約を満たさない。

N個の集合頂点とM個の要素頂点を作り、j∈S_iごとに無向辺を張る。要素1からBFSし、要素Mが未到達なら-1、到達距離をdとすればd/2-1を出力する。

典型の発動条件

incidence graph

発動条件: 集合間の関係が共有要素で定まり、全pairの交差判定が重い。

集合と要素を別種の頂点にし、所属関係だけを辺として共通部分を暗黙に表す。

幅優先探索

発動条件: 全ての所属辺のcostが等しく、必要なmerge回数が最短path長に対応する。

要素1を始点に単位辺BFSを行い、要素Mへの最短交互pathを求める。

問題固有の要素

一つの集合が最初から1とMを含むと二部グラフ距離は2だが操作回数は0であり、答えは単なる距離の半分ではなくd/2-1である。

別の問題へ持ち帰る視点: 補助頂点を挟んだ最短路では、元問題の操作数へ戻すためにpath上の実体数と初期状態を数え直す。

正当性

集合を共通要素で渡る列は要素–集合–要素のpathに対応。距離dのpathはd/2集合を使いそれらをd/2−1回mergeすれば1,M同居になる。逆にmergeで同居する集合列から同程度のpathを取れるので最短二部pathが最小merge。

実装上の注意

  • 集合頂点と要素頂点のindex領域を分離する。BFS距離の偶奇を前提に変換し、M未到達を先に判定して負の式を評価しない。

復習の核

  • 同一集合に1とMがある答え0、集合を二つ使う答え1、共有要素のchain、到達不能を手計算とBFS距離で照合する。

計算量と制約

時間

集合数N、要素上限M、所属総数L=Σ|S_i|。二部BFS O(N+M+L)。

空間

所属辺とdist O(N+M+L)。

制約との対応

公式制約の確認範囲: Time limit: 3 sec; Memory limit: 1024 MiB; Constraints: 1 \le N \le 2 \times 10^5; 2 \le M \le 2 \times 10^5; 1 \le \sum_{i=1}^{N} A_i \le 5 \times 10^5; 1 \le S_{i,j} \le M(1 \le i \le N,1 \le j \le A_i); S_{i,j} \neq S_{i,k}(1 \le j < k \le A_i); All values in the input are integers.

出典

分類・前提・執筆情報

掲載状態: 収録済み

Merge Set の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

主題の単元: 状態グラフのモデリングと探索

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

      主タグ: 状態グラフのモデリングと探索

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

      学習の位置

      体系上の位置: 状態グラフのモデリングと探索

      • 暗黙状態・重みなし辺・訪問条件を定義し、到達判定・最短手数・列挙の目的に応じてBFS・DFS・backtrackingを選べる。

      学習記録

      状況更新: 更新記録なし

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

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

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

      同じ単元の問題