2020-01-11

第5回ドワンゴからの挑戦状予選 2018 D - Square Rotation (赤色, 800 点)

AtCoder AtCoder800点条件の言い換え二分探索二次元平面上のN点の問題いもす法二次元いもす法格子点をmodごとに分類する集計処理ある量を固定して考える累積和二次元累積和赤色diff ARC-like 被覆最小包含・最小被覆を求める

すごく詰め切るのに時間かかった

問題へのリンク

問題概要 (意訳)

二次元平面上に $N$ 個の座標 (格子点) が与えられる。正の整数 $D$ が与えられる。

まず、各座標について「 $x$ 座標を $D$ だけ増減する」「 $y$ 座標を $D$ だけ増減する」という操作を好きなだけ繰り返す。ただし、複数の点が同じ座標に来ることはできない。操作を繰り返して、 $N$ 個の座標がなるべく互いに近い位置にあるようにしたい。

操作後の点の分布全体を囲うことができる正方形の一辺の長さの最小値を求めよ。

制約

$1 \le N \le 10^{5}$
$1 \le D \le 1000$ 　(部分点として $D \le 30$ )

考えたこと

問題を理解するのに時間がかかった。上の意訳は本当はそれなりの証明を経て得られるものだけど、ここではこれで行く。そして、問題は

$D \times D$ の行列が与えられる (各格子点を mod. $D$ で分類して、集計する)
それらの点をうまく配置して全部を囲う正方形の一辺の長さを最小にしたい

という風に言い換えることができる。いかにも二分探索したくなるので判定問題に落として考える。上界は $O(\sqrt{N}D)$ くらいで抑えられるから、判定回数は $O(\log{N} + \log{D})$ かな。

僕の解法

僕はバチャではちょっと面倒な方法でやってしまった。つまり、

mod. D の値が (i, j) であるような各 (i, j) に対して「正方形の左下がどの場所にあったらだめか」というのが高々有限個の長方形区間の和で表せることを利用する
その区間を求めて、いもす法する
最後に、どの mod. D 分類に対しても大丈夫な領域が残っていたら OK

という方針でやった。長方形区間については、座標圧縮して候補列挙してやったものの、ちょっと煩雑だった。各判定の計算量は $O(N^{2})$ となる。でも、毎回考えている長方形区間の個数が数十個あるからちょっと定数倍が重くて、TLE ギリギリ。

#include <iostream>
#include <vector>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;

int D;
int a[1010][1010];

// [x, y) に ..., i-D, i, i+D, i+2D, ... が何個あるか
// [x-i, y-i) に -D, 0, D, ... が何個あるか
long long num(long long x, long long y, long long i) {
    x -= i, y -= i;
    while (x <= 1) x += D, y += D;
    return (y-1) / D - (x-1) / D;
}

int dame[1010][1010];
bool judge(long long d) {
    //vector<vector<long long>> dame(D+1, vector<long long>(D+1, 0));
    memset(dame, 0, sizeof(dame));
    for (int x = 0; x < D; ++x) {
        for (int y = 0; y < D; ++y) {
            long long need = a[x][y];
            long long s = (long long)((long long)(sqrt(need)) + 0.5);
            if (s * s < need) ++s;
            --s;

            if (d < s * D) return false;
            if (d >= (s + 1) * D) continue;

            vector<long long> ax({0, 1, D-1, D}),
                ay({0, 1, D-1, D});

            for (int it = 0; it <= 1; ++it) {
                if (x + it >= 0 && x + it < D)
                    ax.push_back(x + it);
                if (y + it >= 0 && y + it < D)
                    ay.push_back(y + it);
            }
            
            {
                long long kox = x + D*s - d;
                for (int it = 0; it <= 1; ++it)
                    if (kox + it >= 0 && kox + it < D)
                        ax.push_back(kox+it);
                kox = x + D*(s+1) - d;
                for (int it = 0; it <= 1; ++it)
                    if (kox + it >= 0 && kox + it < D)
                        ax.push_back(kox+it);
            }
            {
                long long koy = y + D*s - d;
                for (int it = 0; it <= 1; ++it)
                    if (koy + it >= 0 && koy + it < D)
                        ay.push_back(koy+it);
                koy = y + D*(s+1) - d;
                for (int it = 0; it <= 1; ++it)
                    if (koy + it >= 0 && koy + it < D)
                        ay.push_back(koy+it);
            }

            sort(ax.begin(), ax.end());
            sort(ay.begin(), ay.end());
            ax.erase(unique(ax.begin(), ax.end()), ax.end());
            ay.erase(unique(ay.begin(), ay.end()), ay.end());
            for (int i = 0; i+1 < ax.size(); ++i) {
                for (int j = 0; j+1 < ay.size(); ++j) {
                    long long can = num(ax[i], ax[i] + d+1, x) *
                        num(ay[j], ay[j] + d+1, y);
                    if (can < need) {
                        dame[ax[i]][ay[j]]++;
                        dame[ax[i+1]][ay[j]]--;
                        dame[ax[i]][ay[j+1]]--;
                        dame[ax[i+1]][ay[j+1]]++;
                    }
                }
            }
        }
    }

    for (int i = 0; i < D; ++i)
        for (int j = 0; j < D; ++j)
            dame[i+1][j] += dame[i][j];
    for (int i = 0; i < D; ++i)
        for (int j = 0; j < D; ++j)
            dame[i][j+1] += dame[i][j];
    for (int i = 0; i < D; ++i)
        for (int j = 0; j < D; ++j)
            if (dame[i][j] <= 0)
                return true;
    return false;
}

long long solve() {
    long long left = 0, right = 1LL<<20;
    while (right - left > 1) {
        long long x = (left + right) / 2;
        if (judge(x)) right = x;
        else left = x;
    }
    return right;
}

int main() {
    int N;
    while (cin >> N >> D) {
        memset(a, 0, sizeof(a));
        for (int i = 0; i < N; ++i) {
            int x, y;
            cin >> x >> y;
            a[x%D][y%D]++;
        }
        cout << solve() << endl;
    }
}

想定解法

想定解法では、「正方形の左下を全通り試す」という方向性だった。左下を決めると、

mod. D 分類が (i, j) となるやつらに対して、何個含められるかが求められる (高々 3 パターンしかない、 $a^{2}, a(a+1), (a+1)^{2}$ という形)
D × D 行列について、 $a^{2}, a(a+1), (a+1)^{2}$ 以下となっているかどうかを 0, 1 で表す配列を作って、その累積和をもっておく
そうすると、可能かどうかの判定が $O(1)$ でできる