CODE FESTIVAL 2017 qual A D - Four Coloring

AtCoder CODE FESTIVAL 問題記録 構築ゲー

http://code-festival-2017-quala.contest.atcoder.jp/tasks/code_festival_2017_quala_d

問題概要

H行W列のグリッドを4色で塗り分ける。このときマンハッタン距離がちょうどdのグリッド同士は別の色で塗らなければならない。条件を満たす塗り方をひとつ示せ。

H, W <= 500

解法

(x, y) -> (x+y, x-y)の変換で45度回転させた座標系において(D-1)×(D-1)の正方形を等間隔に敷き詰め、各正方形内のグリッドは隣接する上下左右斜め8つの正方形と異なる色になるように同じ色で塗る。これは以下のように塗ればできる。

010101
232323
010101
232323

最後に回転を戻せば答え。

なぜこれでよいかというと、(x, y) -> (x+y, x-y)の変換で、前者におけるマンハッタン距離が後者におけるチェビシェフ距離と等しくなるため。つまり後者において(D-1)×(D-1)の正方形を同じ色で塗るのは、どの2点を取っても必ずチェビシェフ距離がD未満になるように塗るということに相当する。このようにするとチェビシェフ距離がちょうどDになるようなグリッドが上下左右斜め8近傍の正方形に含まれることになるので、そこを塗り分ければよい、ということになる。

感想

本番で解けなかったんですが、この問題の最大の罠は「なんかいけそうだけど実は正しくないアドホック解法」が無限に湧いてくるところでした。そういう沼から抜け出すにはどうしたらいいんだろうな～

コード (D言語)

import std.stdio, std.array, std.string, std.conv, std.algorithm;
import std.typecons, std.range, std.random, std.math, std.container;
import std.numeric, std.bigint, core.bitop;
     
void main() {
    auto s = readln.split.map!(to!int);
    auto H = s[0];
    auto W = s[1];
    auto D = s[2];
     
    auto N = max(H, W) * 3;
    auto B = new int[][](N, N);
    int[] colors = [1, 2, 3, 4];
     
    for (int i = 0; i * D < N; ++i)
        for (int j = 0; j * D < N; ++j)
            for (int a = 0; a < D; a++)
                for (int b = 0; b < D; b++)
                    if (i * D + a < N && j * D + b < N)
                        B[i*D+a][j*D+b] = colors[i%2*2+j%2];
     
        
    auto ans = new int[][](H, W);
    auto color = " RYGB";
        
    foreach (i; 0..H) {
        foreach (j; 0..W) {
            int ni = i + j;
            int nj = i - j + W;
            ans[i][j] = B[ni][nj];
        }
    }
     
    ans.each!(an => an.map!(a => color[a]).writeln);
}