問題概要

$n \times m (n, m \leq 10^9)$ のグリッドのうち k マスに障害物が置かれている．障害物の位置はそれぞれ $(x_i, y_i)$ である．

次のような条件でグリッド上を動くとき，障害物が置かれていないマスすべてをちょうど1回ずつ訪れることは可能かどうかを答えよ．

(1, 1) からスタート．最初は (1, 2) に向かう方向を向いている．
今見ている方向にしか動けない．違う方向に動きたければ，向きを変える必要がある．1回の動きで90度右に向きを変えられる．
1つのマスでは高々1回しか方向転換できない．

解法概要

問題の条件から，外側から内側に向かって，時計回りに渦巻きを描くようにマスを訪れるのが最適であることがわかる．つまり，行けるところまで行く→右折→行けるところまで行く→右折→……と言うように動くことになる．

f:id:noimin:20191020221543p:plain — 行けるところまで行かずあえて途中で右折した場合

なぜならば，行けるところまで行かず途中で右折した場合，途中で右折したがために寄れなかったマス (図中の塗りつぶし部分) に後で寄るためにはすでに訪れたマスをもう一度訪れる必要があるためである．左回転は不可，同じマスでは1回 (90度) までしか右回転できないという条件を守るにはそうするしかない．

というわけで，「行けるところまで行ったら右折」を繰り返すシミュレーションを書けば良いが，今回はグリッドが最大 $10^9 \times 10^9$ と非常に大きく，盤面全体を配列で持つことはできない．障害物の座標を持った set の二分探索を使って「行けるところまで行く」の「行けるところまで」がどこまでなのかを求める必要がある．また，外側から内側に向かって渦を巻くようにマスを訪れるので，x座標y座標それぞれについての行ける上限/下限も持っておく必要がある．

全部のマスを訪れたかどうかは，訪れたマスの数を数えておけば判定できる．

また，実装によっては最初のマスで初手右回転するパターンがコーナーケースとなるので注意．本番では多くのソースコードがこのパターンで落とされていてすごかった．

ソースコード

#include <iostream>
#include <set>
#include <algorithm>

using namespace std;

using ll =  long long;

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int n, m, k;
    cin >> n >> m >> k;
    int x, y;
    set<int> obstacles_yx[n+1], obstacles_xy[m+1];
    for(int i=0;i<k;++i) {
        cin >> y >> x;
        obstacles_yx[y].insert(x);
        obstacles_xy[x].insert(y);
    }

    int i = 1, di = 0, x2, y2;
    y = 1; x = 1;
    ll rest = ll(n)*ll(m) - k - 1;
    int wall[4] = {m+1, n+1, 0, 1}; // ここより先の右/下/左/上には行けない
    while(rest > 0) {
        obstacles_yx[y].insert(x);
        obstacles_xy[x].insert(y);
        switch(di) {
            case 0: {
                auto itr = obstacles_yx[y].upper_bound(x);
                if(itr == obstacles_yx[y].end()) {
                    x2 = m;
                } else {
                    x2 = (*itr) - 1;
                }
                x2 = min(wall[0]-1, x2);
                if(x2 == x && (y != 1 || x != 1)) {
                    rest = -1;
                    break;
                }
                rest -= x2-x;
                x = x2;
                wall[0] = x2;
                break;
            }
            case 1: {
                auto itr = obstacles_xy[x].upper_bound(y);
                if(itr == obstacles_xy[x].end()) {
                    y2 = n;
                } else {
                    y2 = (*itr) - 1;
                }
                y2 = min(wall[1]-1, y2);
                if(y2 == y && (y != 1 || x != 1)) {
                    rest = -1;
                    break;
                }
                rest -= y2-y;
                y = y2;
                wall[1] = y2;
                break;
            }
            case 2: {
                auto itr = obstacles_yx[y].lower_bound(x);
                if(itr == obstacles_yx[y].begin()) {
                    x2 = 1;
                } else {
                    --itr;
                    x2 = (*itr) + 1;
                }
                x2 = max(wall[2]+1, x2);
                if(x2 == x && (y != 1 || x != 1)) {
                    rest = -1;
                    break;
                }
                rest -= x-x2;
                x = x2;
                wall[2] = x2;
                break;
            }
            case 3: {
                auto itr = obstacles_xy[x].lower_bound(y);
                if(itr == obstacles_xy[x].begin()) {
                    y2 = 1;
                } else {
                    --itr;
                    y2 = (*itr) + 1;
                }
                y2 = max(wall[3]+1, y2);
                if(y2 == y && (y != 1 || x != 1)) {
                    rest = -1;
                    break;
                }
                rest -= y-y2;
                y = y2;
                wall[3] = y2;
                break;
            }
            default:
                break;
        }

        ++di;
        if(di == 4) di = 0;
    }
    cout << ((rest == 0) ? "Yes" : "No") << endl;
    return 0;
}

所感

行ける上限/下限を保持する変数の初期値を正しく設定するのに地味に手間取った．

NoiminのNoise

Codeforces Round #593 Div. 2 D. Alice and the Doll

問題概要

解法概要

ソースコード

所感