ABC 401-500/ABC408E - Minimum OR Path - 競技プログラミング用 知識集積所

---

問題

ABC408E

必要知識

B以下レベルの内容は省略

• UnionFind木（未作成）
• 貪欲法（アルゴリズム系）（未作成）

考え方

ORの結果としてxがあり得るかというのは、xで立っていないビットを持つ道を通らずにゴールできるかということである。
よって、「そのようなxをどのように判定すればよいか」「そのなかで最小値はいくつであるか」を別個に解決すればよい。

まず、「そのようなxをどのように判定すればよいか」。
これは、グラフを最初から作るのではなく、xを決めた後で作ればよい。
ゴールできるかというのはグラフがつながっているかどうかなので、UnionFind木（未作成）を用いれば簡単。

そして、「そのなかで最小値はいくつであるか」については、貪欲法（アルゴリズム系）（未作成）の考えに従って、上位ビットから順に「そのビットを禁止、そこより下位を全部許可したルートがあるか」を判断すればよい。
なぜなら、あるビットを禁止できるのにあえて許可するのは、下位の結果がどうなろうと絶対に得をしないからである。

計算量は、前者は辺の数と同じだけ、後者はビットの桁数だけかかるが、それらを掛け算しても大した数にならないので余裕である。

解答例

解答例

注意点

別解