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)。