ABC429E - Hit and Away

問題概要

問題リンク

$N$頂点$M$辺の単純連結無向グラフ$G$がある。 $G$の各頂点は安全か危険かのどちらかの状態である。 $G$の危険な頂点それぞれについて、次の値を求めよ。

危険な頂点を$v$とする。 相異なる安全な頂点$p, q$を任意にとって、$p$から出発し、$v$を通り、$q$に移動するのにかかる時間の最小値（辺の移動は全てコスト1）

• $N \leq 2 \times 10 ^ 5$
• $M \leq 2 \times 10 ^ 5$
• 安全な頂点が少なくとも2つ存在
• 危険な頂点が少なくとも1つ存在

解法

危険な頂点1つに対して考える。このとき、出発地点、終着地点としてとるべきなのは危険な頂点から1番近い頂点と2番目に近い頂点なので、明らかに危険な頂点からBFSすると解ける。が、これは$O(N(N + M))$時間かかるため間に合わない。 よって、各危険な頂点に距離昇順top2がどの頂点であるかをもっと上手く伝える必要がある。

自分はここでハマってしまったが、おそらく通常のBFSの実装イメージに囚われていると解けない。

上図はサンプル1を図示したものである。 斜線が引かれた頂点3, 4が危険な頂点で、それ以外が安全な頂点になっている。

イメージとしては、危険な頂点には深さ2のくぼみがあり、安全な頂点から一斉に流れ出したそれぞれ違う色の水のうち、どれがくぼみを埋めるか。という感じになる。

例えば1秒後のグラフは少し見にくいが、このようになる。 流れ出した水は隣接頂点へと到達し、この時点で頂点3のくぼみは頂点1と2から流れてきた水で埋められている。

イメージの話は以上で、もう少し細かいことを考える必要がある。 まず、各くぼみには2以下の水しか入らないことから、ある頂点に最初にたどり着いた2つの水以外を考えなくてよいことがわかる。なぜなら、あとから追いついてきた水があったとしても、先行している2人によってどのくぼみも先に埋められてしまうため、意味がないからである。

あとは、今までの話はあたかも危険な頂点にしかくぼみがないかのように言っていたが、上記の議論を考えると、「くぼみを埋めることができた水が次に進む権利を得る」と考えると良さそうだ。 また、どこから来た水であるか（水が何色であるか）という情報も伝播しないと、安全な頂点の始点と終点が相異なるという条件が満たせなくなってしまうので注意が必要である。

だから、通常のグラフ探索が$\mathrm{dist}[i] = \text{$i$に到達する最短距離}$のような情報を管理するのに対して、今回の問題では$\mathrm{info}[i] = \text{現在$i$に到達した水のうち、最初の2つ}$のような情報を管理することになる。 まあ、これ以上は実装を見た方が早いと思うので、実装例を示す。

実装例

import std;

void main () {
    int N, M;
    readln.read(N, M);

    auto U = new int[](M);
    auto V = new int[](M);
    foreach (i; 0 .. M) {
        readln.read(U[i], V[i]);
        U[i]--, V[i]--;
    }

    string S = readln.chomp;

    auto graph = new int[][](N);
    foreach (i; 0 .. M) {
        graph[U[i]] ~= V[i];
        graph[V[i]] ~= U[i];
    }

    auto q = DList!(Tuple!(int, int, int))();

    alias Info = Tuple!(int, int);
    auto top2 = new Tuple!(Info, Info)[](N);
    top2[] = tuple(Info(-1, int.max), Info(-1, int.max));

    foreach (i; 0 .. N) {
        if (S[i] == 'S') {
            top2[i][0] = tuple(i, 0);
            q.insertBack(tuple(i, i, 0));
        }
    }

    while (!q.empty()) {
        auto pos = q.front();
        q.removeFront();

        foreach (to; graph[pos[0]]) {
            if (top2[to][1][0] != -1) {
                continue;
            }

            if (top2[to][0][0] == -1) {
                top2[to][0] = Info(pos[1], pos[2] + 1);
                q.insertBack(tuple(to, pos[1], pos[2] + 1));
                continue;
            }
            if (top2[to][1][0] == -1 && top2[to][0][0] != pos[1]) {
                top2[to][1] = Info(pos[1], pos[2] + 1);
                q.insertBack(tuple(to, pos[1], pos[2] + 1));
                continue;
            }
        }
    }

    auto ans = new int[](0);
    foreach (i; 0 .. N) {
        if (S[i] == 'D') {
            ans ~= top2[i][0][1] + top2[i][1][1];
        }
    }

    writefln("%(%s\n%)", ans);
}

void read (T...) (string S, ref T args) {
    import std.conv : to;
    import std.array : split;
    auto buf = S.split;
    foreach (i, ref arg; args) {
        arg = buf[i].to!(typeof(arg));
    }
}

D言語/218ms

各頂点に2色の水しか来ないことを考えると計算量が抑えられる。 通常のBFSが頂点を1回、辺を2回以下しか見ないこと同様に、このBFSでは頂点を2回、辺を4回以下しか見ない。 だから時間計算量は$O(N + M)$時間である。

考察

この問題ではどの頂点から来た値かを保持しながら伝播していく。逆に言うと、通常の最短経路問題は普通のグラフ探索であれば保持できるはずの情報を捨てているのだということに気づいた。 さらに、最短経路問題では単一の「最短距離」のみを保持するが故、「先に到達した2つ」のようにフレキシブルに調節できるということを知らず知らずのうちに思考から除外していた。

そういう点で面白い問題だったと思う。一般に、DFS系のグラフ探索がパスを生成しているようなものであるのに対し、BFS系のグラフ探索というのは波が広がっているようなものなのだと言えそうだ。それを到達された側の頂点でどう扱うかには幾分の自由度があり、例えば今回のように、1辺に2波までは流せるといった設定にすることも可能だという点が発見だった。

蛇足

1ヵ月に1回は更新したいと思っていたが、気がついたら2ヵ月経っていた。 新しい競プロネタはあるっちゃあるものの、なかなかまとめるのが大変なテーマばかりがあるというのと、AWCに忙殺されているというのがあり、精力的に更新できるかはわからない。

というか、最近は人間と話すことがそれなりに多いこともあり、文章にまとめたい欲がそがれているフシはありそうだ。 まあやる気が出たらぼちぼち更新するので適当に見守って貰えるとありがたい。

あと、おにまいアンソロジー8巻が出るらしいので、人々は買おう。