【AtCoder】ABC 408 E - Minimum OR Path | 緑コーダーが解くAtCoder

atcoder.jp

配点: 450 点 / 実行時間制限: 3 sec / メモリ制限: 1024 MB / Difficulty: 1222 / NoviSteps: 1D

問題概要
制約
考察
実装例
- BFS の利用
- Union-Find の利用
コメント

問題概要

$N$ 頂点 $M$ 辺の自己ループを持たない連結無向グラフが与えられる。辺 $i$ は頂点 $u_i$ と頂点 $v_i$ を双方向に結んでおり、ラベル $w_i$ がつけられている。

頂点 $1$ から頂点 $N$ までの単純パスのうち、パスに含まれる辺につけられたラベルの総ビット単位 $\mathrm{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}$
入力される値は全て整数

考察

ABC396-D で似たような名前の問題は出題されているが、今回は頂点数 $N$ の制約が大きいため、単純パスの全列挙はできない。

そこで、bit演算系の問題の解法の典型「bitごとに考える」を、この場合も適用することを考える。

例として、以下のようなグラフを考える。

初期値として、総 $\mathrm{OR}$ が $11111$ である経路(赤のパス)を考える。

ここから最上位bitを $0$ にできるような経路が存在するか判定する。このケースでは、緑色の経路を辿れば、総 $\mathrm{OR}$ が $01111$ とすることができる。

このようにして、 $2^{30} - 1$ (辺のラベルとしてあり得る最大値)の上位bitから順に $0$ とできるかどうかを試していく。この判定には BFS / DFS あるいは Union-Find を用いることができる。

現在注目している $i$ bit目について、 $0$ にできないならばそのbitは $1$ で値が確定する。

また、既に $0$ で値が確定したbitについて、判定の過程でそのbitが $1$ になるような辺は通過することができない。

以上を踏まえて実装すれば、BFS では $O(N + M)$ 、Union-Find では $O(M \cdot \alpha(N))$ ( $\alpha(N)$ はアッカーマン関数の逆関数) の計算量で答えを求めることができる。

Union-Findの方がコードを書く量は少ないので速そう。実装例ではACLのDSUを用いている。

実装例

BFS の利用

#include <bits/stdc++.h>
using namespace std;

#define rep(i, start, end) for (auto i = (start); (i) < (end); (i)++)
#define rrep(i, start, end) for (auto i = (start); (i) >= (end); (i)--)

template <class T>
using Graph = vector<vector<T>>;

// ======================================== //

struct Edge
{
    int to;
    int cost;
};

int main()
{
    int N, M;
    cin >> N >> M;
    Graph<Edge> G(N);
    rep(i, 0, M)
    {
        int u, v, w;
        cin >> u >> v >> w;
        u--, v--;
        G[u].push_back({v, w});
        G[v].push_back({u, w});
    }

    auto bfs = [&](int limit) -> bool
    {
        vector<bool> visited(N, false);
        queue<int> que;
        que.push(0);
        visited[0] = true;

        while (!que.empty())
        {
            int next = que.front();
            que.pop();

            if (next == N - 1)
            {
                return true;
            }

            for (const auto &e : G[next])
            {
                if (!visited[e.to])
                {
                    if ((e.cost | limit) == limit)
                    {
                        visited[e.to] = true;
                        que.push(e.to);
                    }
                }
            }
        }

        return false;
    };

    int ans = (1LL << 30) - 1;
    rrep(bit, 29, 0)
    {
        if (ans & (1LL << bit))
        {
            int temp = ans & ~(1 << bit);
            if (bfs(temp))
            {
                ans = temp;
            }
        }
    }

    cout << ans << endl;

    return 0;
}

atcoder.jp

Union-Find の利用

#include <bits/stdc++.h>
using namespace std;

#if __has_include(<atcoder/all>)
#include <atcoder/all>
using namespace atcoder;
#endif

#define rep(i, start, end) for (auto i = (start); (i) < (end); (i)++)
#define rrep(i, start, end) for (auto i = (start); (i) >= (end); (i)--)

// ======================================== //

struct Edge
{
    int from;
    int to;
    int cost;
};

int main()
{
    int N, M;
    cin >> N >> M;
    vector<Edge> edges(M);
    rep(i, 0, M)
    {
        cin >> edges[i].from >> edges[i].to >> edges[i].cost;
        edges[i].from--;
        edges[i].to--;
    }

    int ans = (1LL << 30) - 1;
    rrep(bit, 29, 0)
    {
        if (ans & (1LL << bit))
        {
            int temp = ans & ~(1 << bit);
            dsu dsu(N);
            for (auto &&e : edges)
            {
                if ((e.cost | temp) == temp)
                {
                    dsu.merge(e.from, e.to);
                }
            }

            if (dsu.same(0, N - 1))
            {
                ans = temp;
            }
        }
    }

    cout << ans << endl;

    return 0;
}