けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AtCoder AGC 025 D - Choosing Points (赤色, 800 点)

数学(整数問題) 二部グラフ グラフ 構築 AtCoder AtCoder800点 AGC-D ガウス整数 赤色diff パリティ 競技数学色強め 二次元グリッド 市松模様・塗り分け

二部グラフ解法頭いいと思ったものの、整数論的考察で通したのでその報告を。TL 見た限りだと、kirika さんと同じ解法っぽいですがかなり少数派っぽいです (ただし、自分はイデアルという概念を意識できてはいなかったです...)。

AGC 025 D Choosing Points

問題概要

整数 N, D1, D2 が与えられる。以下の条件を満たすサイズ N2 の格子点集合を 1 つ求めよ。

  • どの格子点の x 座標、y 座標も 0 以上 2N 未満
  • どの 2 点を選んでも、その間の距離が √D1 でも √D2 でもない。

制約

  • 1 ≦ N ≦ 300
  • 1 ≦ D1 ≦ 2×105
  • 1 ≦ D2 ≦ 2×105

解法

0 <= x, y < 2N を満たす 4N2 個のうち 1/4 だけ拾って条件を満たすようにする問題です。D1 について条件を満たすようにして半分残して、D2 について条件を満たすようにして半分残すような感じで構成します。

さて、D が 2 で何回割れるかに着目します。

D = 2^{p} * (奇数)

としてみます。この p の値に応じて、以下のように実は 4N2 個の点のうち半分が「どの 2 頂点の距離の平方も D にならない」という条件を満たすようにすることができます:

p の偶奇によって場合分けしていて

  • p が偶数のときは、市松模様っぽく塗ります (市松の大きさが 2p/2 です)
  • p が奇数のときは、縞模様っぽく塗ります (縞の太さが 2p/2 です)

これらは平面上の格子点の個数を概ね半分 (領域が無限大なら丁度半分) にする操作です。気になるのが D1 に格子点をふるいをかけた後に D2 についてふるいをかけたときにも「半分だけ残す操作」になっているのかどうかですが、少し考えれば大丈夫なことがわかります。

なお、上の絵のようなふるいのかけ方でいいことについてですが、 x + yi が (1 + i)^{p} で割り切れるが (1 + i)^{p + 1} では割り切れないことを利用しています。

#include <iostream>
using namespace std;

int N, A[2];
bool ok[1000][1000];

int main() {
    cin >> N >> A[0] >> A[1];
    for (int i = 0; i < 1000; ++i) for (int j = 0; j < 1000; ++j) ok[i][j] = true;

    // 2 で何回割れるか
    int num[2] = { 0 };
    for (int iter = 0; iter < 2; ++iter) {
        num[iter] = 0;
        while (A[iter] % 2 == 0) {
            ++num[iter];
            A[iter] /= 2;
        }
    }

    // 盤面をふるいにかける
    for (int iter = 0; iter < 2; ++iter) {
        int p = num[iter];
        if (p & 1) {
            int two = 1 << (p / 2);
            for (int x = 0; x < N * 2; ++x) {
                for (int y = 0; y < N * 2; ++y) {
                    if (y % (two * 2) >= two) ok[x][y] = false;
                }
            }
        }
        else {
            int two = 1 << (p / 2);
            for (int x = 0; x < N * 2; ++x) {
                for (int y = 0; y < N * 2; ++y) {
                    int px = (x % (two * 2) >= two ? 1 : 0);
                    int py = (y % (two * 2) >= two ? 1 : 0);
                    if (px != py) ok[x][y] = false;
                }
            }
        }
    }

    // N^2 個になるまで出力
    int con = 0;
    for (int x = 0; x < N * 2; ++x) {
        for (int y = 0; y < N * 2; ++y) {
            if (con == N*N) break;
            if (ok[x][y]) {
                cout << x << " " << y << endl;
                ++con;
            }
        }
    }
}

考えたことメモ

共円だあああああああああああ！！！！！！！！！！！！ となりました。この問題を解くにあたって

x^{2} + y^{2} = D

を満たす整数 (x, y) の組がどうなるかが気になるのですが、D を素因数分解して

D = 2^{a} p_1^{k_1} p_2^{k_2} ... p_P^{k_P} q_1^{l_1} q_2^{l_2} ... q_Q^{l_Q} ( p_i は 4 で割って 1 余る素数、 q_i は 4 で割って 3 余る素数)

となったときに、

  • l_j はすべて偶数でない限り 0 通り
  • l_j がすべて偶数のとき、実質 (k_1 + 1)(k_2 + 1)...(k_P + 1) 通り

になることが知られています (実質というのは正負を入れ替えたりするものを除き、x と y を入れ替えたものは含むことにする)。これは実は可換環 Z[i] 上の素因数分解をすると示せるのですが、ここではそういう考察抜きに上のことを事実として認めると、 x^{2} + y^{2} = D を満たす (x, y) の組は場合によってはかなり多彩になることがわかります。

(ものすごく余談なのですが、共円における「32 角形定石」だとか「48 角形定石」だとかはこの方法で簡単に作ることができます。)

このことから、 x^{2} + y^{2} = D を満たす (x, y) の組を列挙して云々という解法ではなさそうだと思いました。

そこで次に「D が何回 2 で割れるか」に着目してあの解法に至りました。