CODE FESTIVAL 2017 qualA D - Four Coloring 解説

感想

AtCoder Problemsの新機能によって勧められたので解いてみた。
諦めようと思ってた所で解けたので気持ちよかった。

問題

https://atcoder.jp/contests/code-festival-2017-quala/tasks/code_festival_2017_quala_d

問題概要

グリッドがある。「マンハッタン距離がちょうどDであるようなマスのペアに異なる色を用いる」という条件の下で、グリッドを4色に塗り分けろ。

思考過程

• 4色問題！4色問題が解けるわけはないと思ったので他の方法を考える。
• Dが奇数のときは市松模様を出力すれば良い。（結局使わなかったけど）
• 明らかに45度回転を要求しそうな問題。この機会に覚えたい。
• 「マンハッタン距離がD」⇔「45度回転した盤面で、中心からの距離がDとなるような正方形」

となる。45度回転した盤面において条件を満たす塗り方は比較的簡単に分かる。（図１）

図１　回転後の盤面における最適な塗り方

• よって、この図を45度逆回転して元に戻すことを考える。
• ここで注意したのは、回転後の盤面には以下のような使われてないマスが半分あるということ。つまり、逆回転したときの形はすこし特殊な形になる。（図２）

  

  図２　回転前の盤面に戻したときの形

よってこれを実装すれば良い。

実装

• 周期D×Dで塗ることになるので、2D×2Dについてのみ考えて、H×Wのグリッドを出力する際にはあまりを求めて塗る色を参照した。

#define p(x) cout<<x<<endl;
#define pu(x) cout<<(x);
#define el cout<<endl;

int main(){
	cin >> h >> w >> d;
	//2d * 2d の周期が繰り返される
	ll syuki = 2 * d;
	for(i=0;i<2*d;i++){
		for(j=0;j<2*d;j++){
			//回転後の盤面の座標によって塗る色を決める
			a = 0;
			if(0 <= (i + j) % syuki && ((i + j) % syuki) < d)a += 2;
			if(0 <= ((i - j + 1000 * syuki) % syuki) && ((i - j + 1000 * syuki) % syuki) < d)a += 1;
			dp[i][j] = a;
		}
	}
	for(i=0;i<h;i++){
		for(j=0;j<w;j++){
			//さっき決めた周期のテーブルを参照する
			a = i % syuki;
			b = j % syuki;
			if(dp[a][b] == 1)pu("R");
			if(dp[a][b] == 2)pu("Y");
			if(dp[a][b] == 3)pu("G");
			if(dp[a][b] == 0)pu("B");
		}
		el;
	}
	return 0;
}

まとめ

こうしてみると突飛な発想を要求する箇所は１つもない……。