はまやんはまやんはまやん

hamayanhamayan's blog

大きなクリスマスプレゼント [パ研合宿2019　第3日「パ研杯2019」 E]

競技プログラミング

https://atcoder.jp/contests/pakencamp-2019-day3/tasks/pakencamp_2019_day3_e

前提知識

解説

https://atcoder.jp/contests/pakencamp-2019-day3/submissions/9144974

クエリ問題では、まず1クエリだとどう解くかを考えるのが定石。
操作の建物と重ならないようにちょうど1メートル動かす操作をする。
これは、プレゼントの左上のマスが今いるマスと考えると、横に1マス移動していることになる。
すると、今回の答えは周りに1マス移動するときに到達可能な頂点の個数となる。
これらの情報からBFSで解けるのではと考える。
制約もそれっぽい。
だが、マスによっては建物とかぶってしまって移動できない。
これを判定するには二次元累積和を使えばO(1)で使えるマスかが判定できる。
これでBFSをすれば、O(HW)では解けそうだ。

これでは満点は狙えない。
Lが変わる問題にどう立ち向かおうか。
さて、ここからブレイクスルーをする必要がある。
UnionFindを使おう。
到達可能な頂点の個数は、隣り合う使える頂点を連結した連結成分に含まれる頂点数と等しくなる。
この考察に至るまで大変だと思う。
あと、ここから更に必要なのが、Lを大きい方から見て、オフライン計算をしていく必要がある。
クエリを事前に読み込んでおき、分類しておこう。
queries[l] := L[i]=lであるクエリのiの集合

次に以下を前計算しておく。
ma[y][x] := 各頂点で置ける最大のプレゼントの大きさ
これは二次元累積和と二分探索をすればO(HWlog(H+W))でできる。
これで「que[l] := ma[y][x]がlである座標の集合」を作っておく。

あとは、Lを大きい方から順番に見ていって、que[l]にある頂点とその周りの頂点が連結できれば連結する。
連結後に、queries[l]に含まれる頂点の連結成分の個数を答える。

int H, W;
string S[1510];
Ruisekiwa2D<1510, 1510> r2d;
int Q;
int X[151010], Y[151010], L[151010];
vector<int> queries[1510];
vector<pair<int, int>> que[1510];
int ma[1510][1510];
int dx[4] = { 0, 1, 0, -1 }, dy[4] = { -1, 0, 1, 0 };
int ans[151010];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> H >> W;
    rep(y, 0, H) cin >> S[y];
    cin >> Q;
    rep(i, 0, Q) cin >> Y[i] >> X[i] >> L[i];

    rep(y, 0, H) rep(x, 0, W) if (S[y][x] == '#') r2d.set(x, y, 1);
    r2d.build();

    rep(i, 0, Q) queries[L[i]].push_back(i);
    rep(y, 0, H) rep(x, 0, W) {
        int len = min(H - y, W - x);
        int ok = 0, ng = len + 1;
        while (ok + 1 != ng) {
            int md = (ok + ng) / 2;
            if (r2d.get(x, x + md - 1, y, y + md - 1) == 0) ok = md;
            else ng = md;
        }
        ma[y][x] = ok;
        que[ma[y][x]].push_back({ x, y });
    }

    UnionFind2D uf(H, W);

    rrep(l, 1500, 1) {
        fore(p, que[l]) {
            int x = p.first;
            int y = p.second;
            rep(d, 0, 4) {
                int xx = x + dx[d];
                int yy = y + dy[d];
                if (0 <= xx and xx < W and 0 <= yy and yy < H) {
                    if (l <= ma[yy][xx]) uf.marge(x, y, xx, yy);
                }
            }
        }
        fore(i, queries[l]) {
            ans[i] = uf.getValue(X[i] - 1, Y[i] - 1);
        }
    }

    rep(i, 0, Q) printf("%d\n", ans[i]);
}