今日の会社のバチャでやった。面白かった。

問題概要

$H \times W$ のグリッドに 'A', 'B', 'C' の各文字を書き込む。以下の条件を満たすものを一つ求めよ。

以下のようなに対してである:
- 隣接する 2 マスの組であって一方が 'A' で他方が 'B' であるものの個数を $p$ とする
- 隣接する 2 マスの組であって一方が 'B' で他方が 'C' であるものの個数を $q$ とする
- 隣接する 2 マスの組であって一方が 'C' で他方が 'A' であるものの個数を $r$ とする
どの行、どの列を見ても、'A', 'B', 'C' の書かれたマスが 1 個以上ある

たとえば $H = W = 4$ のとき、以下が条件を満たす:

A B C A
B C A B
C A B C
A B C A

制約

$H, W \ge 4$

考えたこと

一目面白そう！！！ということで挑んだ。この手の構築で考えたくなることは

なにか簡単でわかりやすい規則で構築を試みる
とりあえず小さいサイズで解いてみて、一般の場合に拡張できないかを考える
数学的帰納法による構築を試みる
- $k$ でできるなら $k+1$ でもできることを示す
- $k$ でできるなら $2k$ でもできて $k-1$ でもできることを示す (ちょっと高度な技)

とかその辺。そうしようと思ったときに、小さいサイズといっても $W, H \ge 4$ という条件がちょっとイヤだな...と思った。

なにか簡単でわかりやすい規則の構築を試みる

ふと思ったのが、

A B C A
A B C A
A B C A
A B C A
A B C A
A B C A
A B C A
...

という感じの構築が、一見条件を満たしてそうだと思った。そしてこれをちょっと拡張すると

A B C A A A ...
A B C A A A ...
A B C A A A ...
A B C A A A ...
A B C A A A ...
A B C A A A ...
...

みたいな感じでイケてるんじゃないかと。でもこれで提出して WA になった。なぜなら、条件のうちの

どの行・どの列をみても 'A', 'B', 'C' の書かれたマスが少なくとも 1 つ以上ある

を満たしていないからだ。

ちょっと変える

というわけなのでしきりなおし。ならば各行ごとに巡回させてみようということで

A B C A
B C A B
C A B C
A B C A

というのを書いてみて、これが条件を満たしていることに気がついた。

A と B の隣接は 11 箇所
B と C の隣接は 11 箇所
C と A の隣接は 11 箇所

になっている。で、よく考えると、これを横にコピーして

A B C A A
B C A B B
C A B C C
A B C A A

としたものも条件を満たしているのだ。なぜなら、横に増やしたことによる影響は

A と B の隣接箇所が 4 箇所増える
B と C の隣接箇所が 4 箇所増える
C と A の隣接箇所が 4 箇所増える

ということで、影響がそれぞれ等しいからだ。同様に

A B C A A A A A ...
B C A B B B B B ...
C A B C C C C C ...
A B C A A A A A ...

としたものも条件を満たす！！！さらにさらに、こうして作ったものを下にコピーして

A B C A A A A A ...
B C A B B B B B ...
C A B C C C C C ...
A B C A A A A A ...
A B C A A A A A ...

としたものも条件を満たしていて、下にコピーを続けて

A B C A A A A A ...
B C A B B B B B ...
C A B C C C C C ...
A B C A A A A A ...
A B C A A A A A ...
A B C A A A A A ...
A B C A A A A A ...
A B C A A A A A ...
A B C A A A A A ...
...

としたものが条件を満たしている。以上から、 $H, W \ge 4$ について構築できた。

提出コード

#include <iostream>
#include <vector>
#include <string>
using namespace std;

vector<string> base = {"ABC", "BCA", "CAB"};

int main() {
    int CASE; cin >> CASE;
    while (CASE--) {
        int H, W; cin >> H >> W;

        vector<string> res(H, "");
        for (int h = 0; h < H; ++h) for (int w = 0; w < W; ++w) res[h] += " ";
        for (int h = 0; h < H; ++h) {
            for (int w = 0; w < W; ++w) {
                if (h < 3 && w < 3) res[h][w] = base[h][w];
                else if (h < 3) res[h][w] = base[0][h];
                else if (w < 3) res[h][w] = base[0][w];
                else res[h][w] = 'A';
            }
        }
        for (int h = 0; h < H; ++h) cout << res[h] << endl;
    }
}