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

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

KUPC 2019 G - ABCのG問題

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

問題へのリンク

問題概要

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

  • 以下のような  p, q, r に対して  p = q = r である:
    • 隣接する 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;
    }
}