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