ABC 335 E — Non-Decreasing Colorful Path

考察

非減少pathではAが小さい頂点から大きい頂点へしか辺を進めず、Aが等しい辺だけは双方向に使える。同じ値の辺で連結な頂点群は、入った場所から任意の出口へ移れてscore増分も一度だけなので一頂点へ縮約できる。等値成分内の移動ではdistinct値数は増えず、異なる値の成分へ移るたび必ず1増える。縮約後の辺は値が厳密増加するためDAGであり、simple path条件もcycleを除いた最長pathの構成を妨げない。

採用する候補: 同値連結成分をDSUで縮約し、値が増えるDAG上で最長path DPを行う

等値cycleを消した後は全辺がAの小さい成分から大きい成分へ向き、値順に安全に遷移できる。

棄却する候補: 元graph上で頂点番号順にdpを更新する

依存順は頂点番号でなくAの大小で決まり、等値辺のcycleもあるため一回の走査では伝播しない。

A_u=A_vの全辺をDSUでunionする。各元辺の異なる代表元間に小さいAから大きいAへの有向辺を作る。頂点1の成分dp=1、他を到達不能として、成分をA昇順に処理しdp[next]=max(dp[next],dp[cur]+1)を行い、頂点Nの成分値を出力する。

典型の発動条件

同値辺のcomponent縮約

発動条件: 同じlabel間の移動が双方向でcost増分0となりcycleを作る。

DSUで同値連結部分をまとめ、内部pathを一状態として扱う。

DAG最長path

発動条件: 縮約後の遷移ごとにlabelが厳密増加し、scoreが1増える。

label昇順をtopological orderとしてdp最大値を伝播する。

問題固有の要素

scoreは訪問頂点数ではなくdistinctなAの数なので、同じAの連結領域を何頂点通っても一段として数える。

別の問題へ持ち帰る視点: 非減少label pathでは、等値移動を0-cost componentへ縮約して厳密増加DAGへ変える。

正当性

等値連結成分内はscoreを増やさず任意出口へ行けるため縮約可能。残る辺は厳密値増加でDAG。各成分の最大scoreを値順更新する帰納法で全非減少pathの最適を得る。

実装上の注意

  • A_1>A_Nなど到達不能なら答え0とする。同じ代表元の辺は捨て、並行辺は残しても正しさは変わらないがdeduplicate可能である。

復習の核

  • 1とNが同じ等値成分、等値cycleから複数出口、値が下がる辺しかない場合を小graphの全simple pathと比較する。

計算量と制約

時間

N 頂点、M 辺。DSU O(Mα(N))、値sort O(N log N)、DAG DP O(N+M)。

空間

縮約graphとDSU・DP O(N+M)。

制約との対応

公式制約の確認範囲: Time limit: 2 sec; Memory limit: 1024 MiB; Constraints: All input values are integers.; 2 \le N \le 2 \times 10^5; N-1 \le M \le 2 \times 10^5; 1 \le A_i \le 2 \times 10^5; The graph is connected.; 1 \le U_i < V_i \le N; (U_i,V_i) \neq (U_j,V_j) if i \neq j.

出典

分類・前提・執筆情報

掲載状態: 収録済み

Non-Decreasing Colorful Path の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

主題の単元: DSUによる連結成分管理・縮約

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

    主タグ: DAGのtopological processing DSUによる連結成分管理・縮約

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

    学習の位置

    体系上の位置: DSUによる連結成分管理・縮約

    • 静的な辺を探索して成分を付けるか、辺追加ごとに成分を併合し、同一成分・サイズを判定できる。
    • 依存辺の向きを定め、入次数またはpostorderからtopological順を作って制約伝播・DP・scheduleを処理する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。

    学習記録

    状況更新: 更新記録なし

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

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

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

    同じ単元の問題