UVA 13076 - The traveller squirrel -

概要

N*Mの領域にあるn本の座標(xi, yi)が与えられる。
(x,y)からは与えられた座標のうち(x±K, y±K)の範囲に含まれる座標、または(0, 0)(N, M)に移動できる。
(0, 0)から(N, M)に移動することを考える。
与えられた順番に座標を取り除いていくとき、(0, 0)から(N, M)に移動できなくなったときの座標を求めよ。

問題文
https://uva.onlinejudge.org/external/130/p13076.pdf

解法

解法1 Union Find

座標を要素としたUnion Find。クエリを後ろから見るやつ。

全ての座標が取り除かれた状態を考えて、与えられた逆順に座標を追加していく。その際に、その座標から半径K以内かつ、与えられた順序が後ろの座標とuniteする。(与えられた順序が前のものはすでに取り除かれていると考えるため) 座標を追加するごとに、(0, 0)と(N, M)が同じグループに属しているか判定し、属していたらそのとき追加した座標を出力する。

ソースコード

struct UnionFind{
    vector<int> r, p;
    UnionFind() {}
    UnionFind(int size) { init(size); }
    void init(int size) {
        r.resize(size, 0);
        p.resize(size, 0);
        for ( int i = 0; i < size; i++ ) r[i] = 1,p[i] = i;
    }
    int find(int x) {
        return (x == p[x] ? x : p[x] = find(p[x]));
    }
    bool same(int x, int y) {
        return find(x) == find(y);
    }
    void unite(int x, int y) {
        x = find(x); y = find(y);
        if ( x == y ) return;
        if( r[x] < r[y] ) swap(x, y);
        r[x] += r[y];
        p[y] = x;
    }
};
 
signed main() {
    int N;
    while ( cin >> N ) {
        int M, K, n;
        Pii t[100010];
        map<Pii, int> ord;
 
        cin >> M >> K >> n;
        Rep(i, n) {
            cin >> t[i].fr >> t[i].sc;
            ord[t[i]] = i;
        }
 
        t[n].fr = 0; t[n].sc = 0;
        t[n+1].fr = N; t[n+1].sc = M;
        ord[t[n]] = n;
        ord[t[n+1]] = n+1;
 
        UnionFind uf(n+2);
        int flag = -1;
        for ( int i = n+1; i >= 0; i-- ) {
            int x = t[i].fr, y = t[i].sc;
            for ( int nx = x-K; nx <= x+K; nx++ ) {
                for ( int ny = y-K; ny <= y+K; ny++ ) {
                    if ( ord.count(Pii(nx, ny)) && ord[Pii(nx, ny)] > i && (x-nx)*(x-nx)+(y-ny)*(y-ny) <= K*K ) {
                        uf.unite(i, ord[Pii(nx, ny)]);
                    }
                }
            }
 
            if ( uf.same(n, n+1) ) {
                flag = i;
                break;
            }
        }
 
        if ( flag != -1 ) cout << t[flag].fr << " " << t[flag].sc << endl;
        else cout << "Never had the chance" << endl;
    }
 
    return 0;
}

解法2 二分探索

求めたい座標を二分探索で決め打ちしてもできるっぽい。
参考(先輩のコード) http://rhodon.u-aizu.ac.jp:8080/arena/submission_log.jsp?no=3744&runID=20216677

反省とか

コンテスト中は読まなかった気がする。
コンテスト後も問題文をずっと勘違いしていた(最初に与えられた座標から最後に与えられた座標に移動することを考えていた)が、先輩のコードを読んでようやく理解できた。
ord.count(Pii(nx, ny))を書かなかったらTLEしたので、mapを使うときは注意が必要。(参照すると要素が初期化される仕様らしい)
あと、flagを0で初期化していて、WAをだしてしまったのがアホすぎた。(0も解の一つとして考えられるときは気を付けよう)