【ABC408】E問題 - Minimum OR Path 考察から実装(c++)まで

AtCoderBeginnerContest408の解説＆感想です。
コンテストリンク

問題一覧

• 【ABC408】A問題 - Timeout　考察から実装(c++)まで
• 【ABC408】B問題 - Compression　考察から実装(c++)まで
• 【ABC408】C問題 - Not All Covered　考察から実装(c++)まで
• 【ABC408】D問題 - Flip to Gather　考察から実装(c++)まで
• 【ABC408】E問題 - Minimum OR Path　考察から実装(c++)まで <- イマココ
• 【ABC408】F問題 - Athletic　考察から実装(c++)まで

E問題 - Minimum OR Path

問題リンク

問題概要

$N$頂点$M$辺からなる、自己ループを持たない連結な無向グラフが与えられる。各辺$i$にはラベル$w_i$がついている。
頂点$1$から$N$までの単純パスのうち、パスに含まれる辺すべてのビット単位$OR$として最小のものを求めよ。

制約

• $ 2 \le N \le 2 \times 10^5 $
• $ N-1 \le M \le 2 \times 10^5 $
• $ 0 \le w_i \lt 2^{30} $

考察

よくわからないので全探索から考えていく。
単純パスを全探索できればそれで終わり。だけど、例えば

• 3頂点で、$1 \rightarrow 2$に$10^5$本の辺、$2 \rightarrow 3$にも$10^5$本の辺

みたいなグラフがあった場合、単純パスの本数は$10^5 \times 10^5$となって全然ダメ。
ということは、枝刈りするなりなんなりして、なんか上手いこと探索しないといけない。

今回の場合「ビット単位$OR$を取る」というのが特殊な状況なので、上手く使えないか考える。
まず、ビット系の典型である「ビットごとに考える」をすると、高い桁のビットはできるだけ使いたくないなぁ、と気づく。$2^{29}$のビットを使う経路と使わない経路があれば、使わない経路の方が全体の$OR$は確実に小さい。
ということは、「そのビットを使うしかないかどうか」を高い桁から順に調べていくとか良さそう。具体的には

• 最終的な答えを入れる変数ansを作っておく
• $2^{29}$ビットを使わない$1$から$N$への経路があるか調べる。
  • ある場合、$2^{29}$ビットが立っている辺を全て消す
  • なければ、ansの29ビットを$1$にして次に行く
• 残った辺を使って、$2^{28}$ビットを使わない$1$から$N$への経路があるか調べる。
  • ある場合、$2^{28}$ビットが立っている辺を全て消す
  • なければ、ansの28ビットを$1$にして次に行く
• $2^{27}$以降も繰り返し

という手順で、使用できる辺を絞りながら、上の桁から下の桁まで全部調べればいい。
「辺の削除」が面倒くさそうなので、notUseBitみたいな変数を作って使用しないビットのビットマスクを作っておけば良さそう。

計算量は、あるビットを使わずに到達できるか？に$O(N)$、チェックするビット数は$O(log(max(w_i)))$なので、全体で$O(Nlog(max(w_i)))$。

実装

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vb = vector<bool>;
using pll = pair<ll,ll>;
using vpll = vector<pll>;
using vvpll = vector<vpll>;

int main(void){
    //入力
    ll N,M;
    cin>>N>>M;
    
    //nexts[u] = {{ラベル、行き先},{ラベル、行き先}...}となるように作る
    vvpll nexts(N);
    for(int i=0;i<M;i++){
        ll u,v,w;
        cin>>u>>v>>w;
        u--; v--;
        nexts[u].push_back({w, v});
        nexts[v].push_back({w, u});
    }
    
    //特定のbitを使わずに1 ~ Nまでたどり着けるか、チェック用の関数
    vb visit(N);
    function<void(ll,ll)> check = [&](ll now, ll notUseBit){
        for(pll next: nexts[now]){
            //削除された辺なら使わない
            if(notUseBit & next.first) continue;
            //行ったことあれば行かない
            if(visit[next.second]) continue;
            
            visit[next.second] = true;
            check(next.second, notUseBit);
        }
    };
    
    ll notUseBit = 0;
    ll ans = 0;
    for(int i=29;i>=0;i--){
        fill(visit.begin(), visit.end(), false);
        visit[0] = true;
        //checkBitを使わずにゴールまで行けるか？
        check(0, notUseBit + (1LL << i));
        
        //たどり着ける場合
        if(visit[N-1]){
            notUseBit += (1LL << i);
        }
        //辿り着けない場合
        else{
            ans += (1LL << i);
        }
    }
    cout<<ans<<endl;
    return 0;
}