CODE FESTIVAL 2017 qual A : D - Four Coloring

問題

H,W,d が与えられる．次を満たすように H\times W のマス目を 4 色で塗り分けよ．

  • マンハッタン距離が d であるような任意の二つのマスについて，それらの色は相異なる

解法

2 つのマス (x_1,y_1), (x_2,y_2) が |x_1-x_2|+|y_1-y_2|=d を満たすとき， (x_1+y_1)-(x_2+y_2)=\pm d または (x_1-y_1)-(x_2-y_2)=\pm d を満たしている．よって

  • (x_1+y_1)-(x_2+y_2)=\pm d のときマス (x_1,y_1), (x_2,y_2) の色は相異なる
  • (x_1-y_1)-(x_2-y_2)=\pm d のときマス (x_1,y_1), (x_2,y_2) の色は相異なる

ようにすればよい．

1 つ目の条件は 2 つの色をつかって塗分けられる．具体的には， (x+y)\%2d が d より小さいか否かで色分けすればよい．

（ H=W=15, d=4 の例）

111100001111000
111000011110000
110000111100001
100001111000011
000011110000111
000111100001111
001111000011110
011110000111100
111100001111000
111000011110000
110000111100001
100001111000011
000011110000111
000111100001111
001111000011110

同様にして，2 つ目の条件も 2 つの色をつかって塗分けられる．

200002222000022
220000222200002
222000022220000
222200002222000
022220000222200
002222000022220
000222200002222
000022220000222
200002222000022
220000222200002
222000022220000
222200002222000
022220000222200
002222000022220
000222200002222

これらを組み合わせればよい（上二つのマスの数を足せばよい）．

311102223111022
331000233310002
332000133320001
322201113222011
022231110222311
002333100023331
001333200013332
011132220111322
311102223111022
331000233310002
332000133320001
322201113222011
022231110222311
002333100023331
001333200013332

4 色で塗り分けるというのを，2 通りの 2 色の塗り分け方を組み合わせて考えるというのは AGC にも出てましたね．