G - ABCのG問題

Contest Duration: 2019-10-13(Sun) 04:00 - 2019-10-13(Sun) 09:00 (local time) (300 minutes)

G - ABCのG問題 Editorial

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : $300$ 点

問題文

$N$ 個のグリッドがあります。 $i\ (1 \leq i \leq N)$ 番目のグリッドの大きさは $H_i$ 行 $W_i$ 列です。 $N$ 個のグリッドそれぞれについて、以下の条件を満たすようにグリッドの各マスに A, B, C のいずれかを書き込んでください。

(一方に A が、もう一方に B が書かれている隣接したマスのペアの個数) $=$
(一方に B が、もう一方に C が書かれている隣接したマスのペアの個数) $=$
(一方に C が、もう一方に A が書かれている隣接したマスのペアの個数)
グリッドの各行・各列に A, B, C はそれぞれ一つ以上書かれている。

ただし、グリッド上の $2$ つのマスは頂点または辺を共有するときに隣接していると見なします。

なお、この問題の制約の範囲で、条件を満たすようなグリッドへの書き込み方が必ず存在することが証明できます。

制約

$1 \leq N \leq 1,000$
$4 \leq H_i \leq 1,000$
$4 \leq W_i \leq 1,000$
$\sum_{i=1}^{N} H_i \times W_i \leq 10^6$
入力は全て整数である。

入力

入力は以下の形式で標準入力から与えられる。

 $N$ 
 $H_1$   $W_1$ 
 $H_2$   $W_2$ 
 $\vdots$ 
 $H_N$   $W_N$

出力

以下の形式で各 $i\ (1 \leq i \leq N)$ ごとに、条件を満たす $H_i$ 行 $W_i$ 列のグリッドを出力せよ。ここで、 $S^i_{yx}\ (1 \leq y \leq H_i, 1 \leq x \leq W_i)$ は $i$ 番目のグリッドの $y$ 行 $x$ 列目に書き込む文字で、A, B, C のいずれかである。

 $S^1_{11}S^1_{12}...S^1_{1W_1}$ 
 $S^1_{21}S^1_{22}...S^1_{2W_1}$ 
 $\vdots$ 
 $S^1_{H_11}S^1_{H_12}...S^1_{H_1W_1}$ 
 $\vdots$ 
 $S^N_{11}S^N_{12}...S^N_{1W_N}$ 
 $S^N_{21}S^N_{22}...S^N_{2W_N}$ 
 $\vdots$ 
 $S^N_{H_N1}S^N_{H_N2}...S^N_{H_NW_N}$

入力例1Copy

Copy

1
4 4

出力例1Copy

Copy

ABCC
CACB
BCAA
CABA

下の図は出力例 $1$ の、A とB、B と C、C と A が書かれた隣接 $2$ マスをそれぞれ赤線、緑線、青線で示しています。赤線、緑線、青線はそれぞれ等しく $10$ 本ずつあり、各行・各列に A, B, C がそれぞれ一つ以上含まれているため、この出力は条件を満たしています。

出力例 $1$ の隣接マス

入力例2Copy

Copy

2
4 5
5 4

出力例2Copy

Copy

CACCB
CBBAA
ACABC
BACBB
BCBA
CAAB
AACB
ABCC
BBCA

出力している $4$ 行 $5$ 列のグリッドと $5$ 行 $4$ 列のグリッドはそれぞれ条件を満たしています。