AtCoder AGC 041 C - Domino Quality (黄色, 900 点)

構築楽しかった

• 問題へのリンク
• editorial

問題概要

のグリッド上に のドミノを互いに重ならないように配置していく。

どの行・列を見ても、その行・列上にある のドミノの個数が互いに等しいような配置を求めよ。存在しない場合は "-1" を出力せよ。

制約

• 

考えたこと

こういうのはとりあえず手を動かしながら考えると良さそう (でも本当は PC 使うのがいいのかも)

のときは明らかにダメ

のときは次のような解がある。

aab
d.b
dcc

これを活用すると の解も得られる

aab...
d.b...
dcc...
...aab
...d.b
...dcc

これで が 3 の倍数の場合は全部できた。こんな風にしてできるパターンを増やして行こう！

一般に、 の場合と の場合ができて、さらに個数も一致している場合、それらを組合せて の場合も作れる。

それ以上

あたりから計画的に挑むことにする。まず 1 個のドミノが置かれたとき、そのドミノが観測される行・列は全部で 3 方向あることに注目する。このことに着目すると

• = 配置されるドミノの総数
• = 各行・列上のドミノの個数

としたとき

となる。 が 3 の倍数でないときは

• 
• 

とするのが良さそうだと検討がつく。よって、 あたりから「各行・列にドミノを 3 個配置」という感じで解を探してみる。

そうすると... で以下の解が見つかった。これらすべてにおいて、各行・列のドミノの個数が 3 個で等しいことに注意する。

のとき

aacd
bbcd
ghee
ghff

のとき

aabbc
hii.c
h..jd
g..jd
gffee

のとき

aabbcc.
ggh...d
j.h...d
jii...e
...kkle
...n.le
...nmmf

一般の へ

と ができたので、実はほとんどの でできることがわかる！！！4 と 5 は互いに素なので

を満たす整数 はかならず存在する。ただしそれが非負整数であるとは限らないので注意。一応確認するとこの作り方でダメなので

• 
• 
• 

の 3 ケースのみ。 はすでにできている。 の場合は の合成で OK。

コード

#include <bits/stdc++.h>
using namespace std;

void put3(vector<string> &fi, int left) {
    vector<string> mask({"aab", "d.b", "dcc"});
    for (int i = left; i < left+3; ++i) {
        for (int j = left; j < left+3; ++j) {
            fi[i][j] = mask[i-left][j-left];
        }
    }
}

void put4(vector<string> &fi, int left) {
    vector<string> mask({"aacd", "bbcd", "ghee", "ghff"});
    for (int i = left; i < left+4; ++i) {
        for (int j = left; j < left+4; ++j) {
            fi[i][j] = mask[i-left][j-left];
        }
    }
}

void put5(vector<string> &fi, int left) {
    vector<string> mask({"aabbc", "hii.c", "h..jd", "g..jd", "gffee"});
    for (int i = left; i < left+5; ++i) {
        for (int j = left; j < left+5; ++j) {
            fi[i][j] = mask[i-left][j-left];
        }
    }
}

void put7(vector<string> &fi, int left) {
    vector<string> mask({"aabbcc.", "ggh...d", "j.h...d", 
                        "jii...e", "...kkle", "...n.lf", "...nmmf"});
    for (int i = left; i < left+7; ++i) {
        for (int j = left; j < left+7; ++j) {
            fi[i][j] = mask[i-left][j-left];
        }
    }
}

long long extGCD(long long a, long long b, long long &x, long long &y) {
    if (b == 0) { x = 1; y = 0; return a; }
    long long d = extGCD(b, a%b, y, x);
    y -= a/b * x;
    return d;
}

vector<string> solve(int N) {
    if (N <= 2) return vector<string>(1, "-1");
    vector<string> res(N, string(N, '.'));

    if (N == 3) put3(res, 0);
    else if (N == 6) put3(res, 0), put3(res, 3);
    else if (N == 7) put7(res, 0);
    else if (N == 11) put7(res, 0), put4(res, 7);
    else {
        long long x, y;
        extGCD(4, 5, x, y);
        x *= N, y *= N;
        while (x < 0) x += 5, y -= 4;
        while (y < 0) x -= 5, y += 4;
        int left = 0;
        for (int i = 0; i < x; ++i) {
            put4(res, left);
            left += 4;
        }
        for (int i = 0; i < y; ++i) {
            put5(res, left);
            left += 5;
        }
    }
    return res;
}

int main() {
    int N;
    while (cin >> N) {
        const auto &res = solve(N);
        for (auto str : res) cout << str << endl;
    }
}