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; }
