BAPC 2018 D - Driver Disagreement

問題

Dashboard - 2018 Benelux Algorithm Programming Contest (BAPC 18) - Codeforces

問題概要

個の交差点がある。交差点は道が二手に分かれており、左に行くと交差点に、右に行くと交差点に辿り着くことが分かっている。また、交差点からピサの斜塔が見える時は、見えない時はという情報がある。

今、自分が交差点かのどちらかにいることが分かっている。そこから左右の選択を適切にすることによって、ピサの斜塔が見えるかどうかの情報から最初に自分がかのどちらにいたのかを特定することは可能か。不可能ならばindistinguishableと答え、可能ならば最短の操作回数を答えよ。

• 
• 
• 
• 

アイデア

一番素直な方法として思いつくのが今いる位置のペアを管理しながらBFSをするというものだが、これは状態が個あるので、TLEしてしまう。 簡単のために、まずindistinguishableなのかどうかだけを考えてみる。

以下では、問題をグラフとして置き換え、ピサの斜塔が見える頂点を黒、見えない頂点を白と呼ぶことにする。

頂点とがindistinguishableであることの意味について考えてみると、どのように移動してもそのペアの頂点の色は等しいということになる。 つまり、仮想的には同じ頂点にいると考えてしまってもいいと言える。

今、とがindistinguishable、かつとがindistinguishableであるということが分かっているとすると、との関係に注目したとき、直感的にはわざわざチェックするまでもなくindistinguishableなのでは？と思える。

実際にこれは正しい。 とがindistinguishableではないとすると、ある操作(例えば、LLRLRみたいな)によって、の方は黒、の方は白の頂点にいるという状況が発生しうる。 しかし、上の2つの仮定から、は黒でもあり白でもあるということになってしまうが、これはあり得ない。

この同値関係が成り立つことを利用して、BFSの状態を減らすことを考える。 以下のBFSではindistinguishableでないペアが見つかり次第ストップするということを前提とする。 「既に2つの状態：と をチェック済みである場合はをindistinguishableであるとしてそれ以降はチェックしない」というBFSを行う。

これはちゃんと機能するBFSとなる。 もし、本当にがindistinguishableなのであればやっていることは正しいし、 が本当は区別可能だったとすると、BFSがとの両方をパスしてしまっていることに反してしまうからである。

このような状態を効率よく管理するためには、UnionFindなどのデータ構造を使えば良い。 この状態のマージによって、BFS内で訪れる状態は個となり、十分に速い。 元の問題に戻ると、区別可能な時は最短の回数が必要になるので、BFS内で同時に回数も管理する。

実装(C++)

#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define fi first
#define se second

struct UF{
    int n;
    //正だったらその頂点の親,負だったら根で連結成分の個数
    vector<int> d;
    UF() {}
    UF(int N):n(N), d(N,-1){}
    int root(int v){
        if(d[v]<0) return v;
        return d[v]=root(d[v]);
    }
    bool unite(int X,int Y){
        X=root(X); Y=root(Y);
        if(X==Y) return false;
        if(size(X) < size(Y)) swap(X,Y);
        d[X]+=d[Y];
        d[Y]=X;
        return true;
    }
    int size(int v){ return -d[root(v)]; }
    bool same(int X,int Y){ return root(X)==root(Y); }
};

int main(){
    int n,A,B;
    scanf(" %d %d %d", &n, &A, &B);

    vector<int> l(n),r(n),t(n);
    rep(i,n) scanf(" %d %d %d", &l[i], &r[i], &t[i]);

    UF uf(n);
    using P = pair<pair<int,int>,int>;
    queue<P> que({ {{A,B},0} });
    while(!que.empty()){
        P now = que.front();
        que.pop();
        int x = now.fi.fi, y = now.fi.se, d = now.se;

        if(t[x] != t[y]){
            printf("%d\n", d);
            return 0;
        }

        if(!uf.unite(x,y)) continue;
        que.push({{l[x],l[y]}, d+1});
        que.push({{r[x],r[y]}, d+1});
    }
    printf("indistinguishable\n");
    return 0;
}