KUPC 2024 B - Brindled Torus (2D)

極端な場合を考えて考察した！

• 問題へのリンク

問題概要

非負整数 (片方は正) が与えられるので、以下の条件を満たすような二次元グリッドを構築せよ（存在しない場合は、そのことを報告せよ）。

• グリッドのマス数は 以上 以下
• グリッドの各マスは白色または黒色であり、その個数の比は である
• グリッドの各マスについて、そのマスに隣接するマスのうち少なくとも一つは、そのマスと異なる色で塗られている（ここでいう隣接はトーラス上のグリッドの意味）

制約

• 

考えたこと

の場合には自明に市松模様が条件を満たす。まず考えたことは、 が 1 : 1 に近いほど、楽に構築できるのだろうということだった。

そこで、次のように考えた。

• とりあえず、簡単のため、 としても一般性を失わない（ の場合は、あとで白黒反転する）
• 「 がある値より大きいときは構築できない」という構造になっていると思われるので、その値を見つけよう！

ここで着目したことは、色の塗り方に関する条件は、次のように言い換えても同じだということだった。

---

グリッドからどの十字 5 マスを選んでも、2 種類以上の色が含まれる

---

このように言い換えるとわかりやすい。 が最も偏るのは

の場合だろうと想像がついた。つまり、どの十字 5 マスを選んでも、白マスが 1 個で黒マスが 4 個である場合である。まずは、これを実際に作れるかを考えた。そうしたら、次のものが作れた。

これがうまくいく理由を簡単に考える。各マスを と表したとき、十字の 5 マスはどこを選んでも「 を 5 で割ったあまり」が 0, 1, 2, 3, 4 を 1 回ずつ登場するようになっていることに着目しよう。

したがって、 グリッドのうち、 が 5 で割り切れるようなマス を黒マスにすると、上手く行くことがわかる。また同様の理由から、 でなくても、一般に、 が 5 で割り切れるようなマス を黒マスにすると、条件を満たすことがわかる。

残り

あとは、 の場合に具体的に構築してあげればよい。いろんなやり方がありそうだが、僕は次のようにした。

---

• 上の グリッドを 1 ブロックとして、これを縦に 2 個、横に 個配置した（マス数は全部で である）
• このとき、黒色マスが 個しかないので、 個になるまで、黒色マスを増やしていく
• 具体的には、 行目の白色マスについては、すべて黒色にしても大丈夫であることに着目して、そこから 個適当に選んで黒色に塗る

---

具体例として、 のとき、次のようになる。

@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
..@....@....@....@....@....@....@....@....@....@....@....@..
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
.@....@....@....@....@....@....@....@....@....@....@....@...
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@.@....@....@....@.
@....@....@....@....@....@....@....@....@....@....@....@....
..@....@....@....@....@....@....@....@....@....@....@....@..
....@....@....@....@....@....@....@....@....@....@....@....@
.@....@....@....@....@....@....@....@....@....@....@....@...
...@....@....@....@....@....@....@....@....@....@....@....@.

コード

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

// 構築した解の checker (提出には必要ない)
bool check(const vector<string> &res, long long A, long long B) {
    const vector<int> dx = {1, 0, -1, 0};
    const vector<int> dy = {0, 1, 0, -1};
    int H = res.size(), W = res[0].size();
    long long anum = 0, bnum = 0;
    for (int i = 0; i < res.size(); i++) {
        for (int j = 0; j < res[i].size(); j++) {
            if (res[i][j] == '.') anum++;
            else bnum++;

            bool ok = false;
            for (int d = 0; d < 4; d++) {
                int ni = (i + dx[d] + H) % H;
                int nj = (j + dy[d] + W) % W;
                if (res[ni][nj] != res[i][j]) ok = true;
            }
            if (!ok) {
                return false;
            }
        }
    }
    return (A * bnum == B * anum);
}

void solve() {
    long long A, B;
    cin >> A >> B;
    bool rev = false;

    // A >= B として一般性を失わない
    if (A < B) {
        swap(A, B);
        rev = true;
    }

    // 明らかに不可の場合 (B = 0 の場合もダメ)
    if (A > 4 * B) {
        cout << -1 << endl;
        return;
    }

    // まずは白黒比が 1 : 4 の 10 x 50(A + B) グリッドを作る
    vector<string> base = {"@....", "..@..", "....@", ".@...", "...@."};
    vector<string> res(10);
    for (int i = 0; i < 10; i++) {
        for (int j = 0; j < A + B; j++) res[i] += base[i % 5];
    }

    // 追加で必要な黒色マス数
    int rem = B * 50 - (A + B) * 10;
    for (int i = 0; i < 10 && rem; i += 2) {
        for (int j = 0; j < res[i].size() && rem; j++) {
            if (res[i][j] == '@') continue;
            res[i][j] = '@';
            rem--;
        }
    }

    // もし白黒判定が必要ならば、白黒判定する
    if (rev) {
        swap(A, B);
        for (int i = 0; i < 10; i++) {
            for (int j = 0; j < res[i].size(); j++) {
                if (res[i][j] == '.') res[i][j] = '@';
                else res[i][j] = '.';
            }
        }
    }
    
    cout << res.size() << " " << res[0].size() << endl;
    for (int i = 0; i < 10; i++) cout << res[i] << endl;
}

int main() {
    int T;
    cin >> T;
    while (T--) solve();
}