ABC 408 E — Minimum OR Path

考察

mask x に含まれる bit だけをもつ辺、すなわち w OR x=x の辺だけで 1 から N へ到達できれば、その経路の OR も x の submask である。

到達可能な mask の集合は bit を追加する方向に単調であるため、上位 bit から 0 にできるか試すことで数値として最小の mask を確定できる。

採用する候補: 全30 bitを立てた mask から上位 bit を順に仮消去し、許可辺だけの DSU connectivity が保たれるなら消去を確定する

棄却する候補: 各頂点に数値として最小の OR 値を一つだけ持つ Dijkstra 風緩和

数値が小さい mask が bit 集合として別 mask の subset とは限らず、途中の最小値一つが将来の辺との OR に対して常に優越するとは限らない。

ans=(1<<30)-1 とする。b=29..0 について cand=ans without bit b を作り、(w_i|cand)==cand の辺だけで DSU を再構築する。1,N が連結なら ans=cand とし、最後の ans を出力する。

典型の発動条件

bit ごとの貪欲最小化

発動条件: 実行可能 mask が bit 追加に対して上向き閉集合で、数値最小を求めるとき。

最上位から各 bit を外した候補の実行可能性を判定する。

submask 制約の connectivity

発動条件: path 上の全 edge label の OR を指定 mask 以下に抑えたいとき。

label の立っている bit が mask にすべて含まれる辺だけ残して連結性を見る。

DSU

発動条件: 同じ edge filter で無向グラフの二点連結性だけ判定したいとき。

候補 mask ごとに初期化し、許可辺の端点を union する。

問題固有の要素

OR の値を path cost として直接比較せず、「この bit 集合だけで通れるか」という decision problem にすると単調性が現れる。

別の問題へ持ち帰る視点: bitwise 集約量の最小化では、候補 mask が許可する要素集合を作り、実行可能性 oracle と上位 bit 貪欲を組み合わせる。

正当性

simple path 条件は connectivity 判定を妨げない。許可辺で walk があれば cycle を除いて simple path にでき、その OR は増えない。 ある候補 x が可能なら x に bit を足した mask も同じ経路を許すので、lexicographic な bit 最小化と同様に高位から貪欲決定できる。 各判定は edge label が候補 mask の submask かを調べて DSU で結ぶだけで、全体 O(30(N+M)α(N)) になる。

実装上の注意

  • label は bit 0..29 だけなので初期 mask を正確に 2^30-1 とする。各 bit 判定で DSU を初期化し直し、禁止 bit を一つでも含む辺を混ぜない。

復習の核

  • 重み0だけの path、低位bitの少ない値と高位bitのある値が競合する path、bridge に特定bitが必要な例を全 simple path 列挙と比較する。

計算量と制約

時間

O(B(N+M)α(N))、B=30、各bit候補をDSUで判定。

空間

O(N+M)。

制約との対応

公式制約の確認範囲: Time limit: 3 sec; Memory limit: 1024 MiB; Constraints: 2\le N\le 2\times 10^5; N-1\le M\le 2\times 10^5; 1\le u_i < v_i\le N; 0\le w_i< 2^{30}; The given graph is connected.; All input values are integers.

出典

分類・前提・執筆情報

掲載状態: 収録済み

Minimum OR Path の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

主題の単元: bitwise greedyによるmask最適化

主題
  • bitwise greedyによるmask最適化: 上位bitから候補maskを仮定し、残り問題のfeasibility oracleでそのbitを保持/除去できるか決める。その発動条件、正当性、計算量を説明し、未知問へ実装できる。
追加で学ぶ技能
    なし
    既習技能

    主タグ: bitwise greedyによるmask最適化

    補助タグ: DSUによる連結成分管理・縮約 貪欲法と交換論

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

    学習の位置

    体系上の位置: bitwise greedyによるmask最適化

    • 上位bitから候補maskを仮定し、残り問題のfeasibility oracleでそのbitを保持/除去できるか決める。その発動条件、正当性、計算量を説明し、未知問へ実装できる。

    先に読む単元:

    • DSUによる連結成分管理・縮約 — 辺追加や同値関係をDSUで統合し、成分代表と必要な成分metadataを一貫して保つ。その発動条件と正当化原理を比較可能な独立教材として学ぶ。
    • 交換論から選択順を導く — 局所選択を交換論で正当化し、候補を安全に確定できる順序を導く。

    学習記録

    状況更新: 更新記録なし

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

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

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

    同じ単元の問題