Square Rotation [Dwango Programming Contest V / 第5回ドワンゴからの挑戦状予選 D]

https://beta.atcoder.jp/contests/dwacon5th-prelims/tasks/dwacon5th_prelims_d

解説

https://beta.atcoder.jp/contests/dwacon5th-prelims/submissions/3665682

公式放送、公式解説通りに実装した解法を紹介する。
ただ、時間が結構ギリギリなので、アルゴリズム理解として見るといいかもしれない。
　
main関数内
入力を取ってきて、cnt[x%D][y%D]を構築している。
あとは、二分探索で答えを導こう。
ok-1を答えているのは、正方形の１辺の座標の個数で二分探索しているので、
正方形の長さ的には個数-1を答えている。
　
check関数内

    int a = r / D;
    int b = r % D;

解説どおりa,bを取ってくる。

    rep(y, 0, D * 2) rep(x, 0, D * 2) {
        int xx = x % D, yy = y % D;
        if (1LL * a * a < cnt[yy][xx]) {
            aa.set(x, y, 1);
        }
        if (1LL * a * (a + 1) < cnt[yy][xx]) {
            ab.set(x, y, 1);
        }
        if (1LL * (a + 1) * (a + 1) < cnt[yy][xx]) {
            bb.set(x, y, 1);
        }
    }
    aa.build(); ab.build(); bb.build();

aa := a*aを超える頂点数がある座標を1としたときの累積和
ab := a*(a+1)を超える頂点数がある座標を1としたときの累積和
bb := (a+1)*(a+1)を超える頂点数がある座標を1としたときの累積和
を作る。座標の左下を全探索するので、縦横2倍の領域をとっておき、同じ盤面を4つ敷き詰めると実装が楽。
ここをうまく処理するともっと高速化できそう。
　

    rep(sy, 0, D) rep(sx, 0, D) {
        int ok = 1;
        if (0 < b) {
            if (bb.get(sx, sy, sx + b - 1, sy + b - 1)) ok = 0; // 左下
            if (ab.get(sx, sy + b, sx + b - 1, sy + D - 1)) ok = 0; // 左上
            if (ab.get(sx + b, sy, sx + D - 1, sy + b - 1)) ok = 0; // 右下
        }
        
        if (aa.get(sx + b, sy + b, sx + D - 1, sy + D - 1)) ok = 0; // 右上
        if (ok) return 1;
    }

解説放送ではなく、解説書の方に書いてある図を参考に四箇所をチェックしていく。
このへんは解説書を参考にしたほうがいい、解説放送も見方を変えただけで同じことを言っているが。
累積和を取得して、1つでもあれば、オーバーしている座標があるということなので、ダメ。
全部のチェックを通ればOK。

int N, D, X[101010], Y[101010];
//---------------------------------------------------------------------------------------------------
int cnt[1010][1010];
Ruisekiwa2D<int, 2010, 2010> aa, ab, bb;
int check(int r) {
    aa.reset();
    ab.reset();
    bb.reset();
 
    int a = r / D;
    int b = r % D;
 
    rep(y, 0, D * 2) rep(x, 0, D * 2) {
        int xx = x % D, yy = y % D;
        if (1LL * a * a < cnt[yy][xx]) {
            aa.set(x, y, 1);
        }
        if (1LL * a * (a + 1) < cnt[yy][xx]) {
            ab.set(x, y, 1);
        }
        if (1LL * (a + 1) * (a + 1) < cnt[yy][xx]) {
            bb.set(x, y, 1);
        }
    }
    aa.build(); ab.build(); bb.build();
 
    rep(sy, 0, D) rep(sx, 0, D) {
        int ok = 1;
        if (0 < b) {
            if (bb.get(sx, sy, sx + b - 1, sy + b - 1)) ok = 0;
            if (ab.get(sx, sy + b, sx + b - 1, sy + D - 1)) ok = 0;
            if (ab.get(sx + b, sy, sx + D - 1, sy + b - 1)) ok = 0;
        }
        
        if (aa.get(sx + b, sy + b, sx + D - 1, sy + D - 1)) ok = 0;
        if (ok) return 1;
    }
 
    return 0;
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> D;
    rep(i, 0, N) cin >> X[i] >> Y[i];
    rep(i, 0, N) cnt[Y[i] % D][X[i] % D]++;
 
    int ng = 1, ok = inf;
    while (ng + 1 != ok) {
        int md = (ng + ok) / 2;
        if (check(md)) ok = md;
        else ng = md;
    }
    cout << ok - 1 << endl;
}

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

hamayanhamayan's blog

Square Rotation [Dwango Programming Contest V / 第5回ドワンゴからの挑戦状予選 D]

解説