Kazun の競プロ記録

競技プログラミングに関する様々な話題を執筆します.

AtCoder Beginner Contest 250 B問題 Enlarged Checker Board

AtCoder ABC ABC250 B問題 200 pts

問題

提出解答

問題の概要

縦 $A$ 行, 横 $B$ 列からなるタイルを縦に $N$ 行, 横に $N$ 列分貼った.

白のタイルの隣には黒のタイル, 黒のタイルの隣には白のタイルを貼る. また, 右上のタイルは白であるとする.

このとき, 縦 $AN$ 行, 横 $BN$ 列の各マス目について, そのマスには白のタイルが貼られているか? 黒のタイルが貼られているか?

制約

$1 \leq N,A,B \leq 10$

解法

各マスがどの何列目, 何行目かのタイルかを調べる. $i$ 行目のマスは $\left \lceil \dfrac{i}{A} \right \rceil$ 行目のタイルである. 列についても同様に求める事ができる.

以上から, マス $(i,j)$ の色は

$\left \lceil \dfrac{i}{A} \right \rceil+\left \lceil \dfrac{j}{B} \right \rceil$ が偶数 $\iff$ 白
$\left \lceil \dfrac{i}{A} \right \rceil+\left \lceil \dfrac{j}{B} \right \rceil$ が奇数 $\iff$ 黒

である. 計算量は各マスで $O(1)$ なので, 全体で $O(HW)$ である.