D: Four Coloring - CODE FESTIVAL 2017 qual A

code-festival-2017-quala.contest.atcoder.jp

距離dが与えられる。マンハッタン距離がdの点同士は異なる色で塗られるように格子点を塗り分けたい。塗り分けを一つ構成せよ。

マンハッタン距離を考えるときは、必ず45度回転を考える。そうすると、x軸またはy軸方向の差のうち、小さいほうがdという条件になる。

これを考えると、まずd=1の場合は、一列ごとにRGRGRGRG...とBYBYBYBY...という塗り分けをすればいいことがわかる。d>=2のときは、R 1個が2*2行列になっているようなイメージである。(p, q)を45度回転済みの座標とすると、

x = (p % (d*2)) / d

y = (q % (d*2)) / d

c = (x * 2 + y) % 4

とすることで、cが0～3が決まる。このインデックスに応じて、RGBYを塗り分ければ良い。O(HW)。