AtCoder Grand Contest 025: D - Choosing Points
https://atcoder.jp/contests/agc025/tasks/agc025_d
問題概要
正整数N, D1, D2が与えられる。xy平面上で 0 <= x < 2N, 0 <= y < 2N に存在する整数座標の点の集合であって、要素数がN2個でありかつ集合の中のどの2点を取ってもその2点の距離がsqrt(D1)でもsqrt(D2)でもないという条件を満たす集合をひとつ構成せよ。このような集合は必ず存在する。
N <= 300
D1, D2 <= 2*105
解法
2次元平面上で距離が定数Dであるような整数座標の点を繋いでできるグラフは必ず2部グラフになる。sqrt(D1), sqrt(D2)でそれぞれこのような2部グラフを作った上でそれぞれの点を2色で塗り分けると、すべての点は以下の4種類のいずれかひとつに分類されることになる。
- D1のグラフで色1, D2のグラフで色1
- D1のグラフで色1, D2のグラフで色2
- D1のグラフで色2, D2のグラフで色1
- D1のグラフで色2, D2のグラフで色2
作ったグラフの性質上、これら4つの集合においては集合内のどの相異なる2点を持ってきてもそれらの距離がsqrt(D1), sqrt(D2)になることはない(その距離になるためには元のグラフで隣接している必要があるが、2部グラフで同色になるならば隣接ではありえない)。
また鳩の巣原理よりこれら4つの分類のうち必ずひとつ以上には (全体の点の数 / 4) 個以上の点が属することになる。この問題で考えるべき格子点は4N2個なので、これらのうち必ずひとつはN2個以上になる。よってそれを答えとすればよい。
なおグラフを作るのを愚直にやるとO(N4)になってしまうが、最初に「原点からの距離がsqrt(D1), sqrt(D2)となる整数座標の点」を前計算で列挙しておけば、これは各x座標においてたかだか2点しか存在しないので、各点においてO(N)で距離sqrt(D1), sqrt(D2)の点が列挙できるためO(N3)で済む。
作ったグラフが必ず2部グラフになることの証明は公式解説に詳しい。
感想
わかりません…… 格子点をある定数の距離で結ぶと2部グラフになる は覚えとくとべんりそう
あと参考にした解説記事 (AtCoder Grand Contest 025 - Unhappy Go Lucky!) で印象に残った文章があるので教訓として引用しときます
まずは 与えられたグラフの特徴を考察 する。独立集合は、二部グラフであれば楽勝で取れる。これが「独立集合」と聞いた瞬間に「二部グラフでは」と行かないと辛い。 AtCoder Grand Contest 025 - Unhappy Go Lucky!
コード (D言語)
import std.stdio, std.array, std.string, std.conv, std.algorithm; import std.typecons, std.range, std.random, std.math, std.container; import std.numeric, std.bigint, core.bitop, core.stdc.string; void main() { auto s = readln.split.map!(to!int); auto N = s[0]; auto D = [s[1], s[2]]; auto G = new int[][][](2, 4*N*N); auto C = new int[][](2, 4*N*N); C[0][] = C[1][] = -1; auto xyd = new int[][](2, 2*N); foreach (i; 0..2) { xyd[i][] = -1; foreach (x; 0..2*N) { foreach (y; 0..2*N) { if (x*x+y*y == D[i]) { xyd[i][x] = y; } } } } foreach (i; 0..2) { foreach (x1; 0..2*N) { foreach (y1; 0..2*N) { foreach (x2; x1..2*N) { if (xyd[i][x2-x1] == -1) continue; foreach (k; [-1, 1]) { int y2 = y1 + k * xyd[i][x2-x1]; if (y2 < 0 || y2 >= 2*N) continue; G[i][x1*2*N+y1] ~= x2*2*N+y2; G[i][x2*2*N+y2] ~= x1*2*N+y1; } } } } } foreach (i; 0..2) { foreach (x1; 0..2*N) { foreach (y1; 0..2*N) { if (C[i][x1*2*N+y1] == -1) { dfs(x1*2*N+y1, 0, G[i], C[i]); } } } } int cnt = 0; foreach (i; 0..2) { foreach (j; 0..2) { if (iota(4*N*N).map!(k => C[i][k] == i && C[j][k] == j).sum < N*N) continue; foreach (x; 0..2*N) { foreach (y; 0..2*N) { if (C[0][x*2*N+y] == i && C[1][x*2*N+y] == j) { writeln(x, " ", y); ++cnt; if (cnt >= N * N) { return; } } } } } } } void dfs(int n, int c, ref int[][] G, ref int[] C) { if (C[n] != -1) return; C[n] = c; foreach (m; G[n]) if (C[m] == -1) dfs(m, c^1, G, C); }