kmjp's blog

競技プログラミング参加記です

CODE FESTIVAL 2017 Qual A : D - Four Coloring

Aはしんどかった。
http://code-festival-2017-quala.contest.atcoder.jp/tasks/code_festival_2017_quala_d

問題

H*Wのグリッドがある。
各マスを4色のいずれかで塗ることを考える。
マンハッタン距離がDのマス同士が同じ色にならないよう色分けせよ。

解法

Dが奇数の場合、市松模様状に塗り分ければよい。
以下Dが偶数の場合を考える。

マンハッタン距離ではなく、X座標とY座標いずれかがD離れた場合に必ず色が異なるようになる構成を考えよう。
例えばD=4のとき、以下のように塗れば条件を満たす。

RRRGRGGGBBBBYYYYRRRRGGGG
RRRGRGGGBBBBYYYYRRRRGGGG
RRRGRGGGBBBBYYYYRRRRGGGG
RRRGRGGGBBBBYYYYRRRRGGGG
BBBBYYYYRRRRGGGGBBBBYYYY
BBBBYYYYRRRRGGGGBBBBYYYY
BBBBYYYYRRRRGGGGBBBBYYYY
BBBBYYYYRRRRGGGGBBBBYYYY
RRRGRGGGBBBBYYYYRRRRGGGG
RRRGRGGGBBBBYYYYRRRRGGGG
RRRGRGGGBBBBYYYYRRRRGGGG
RRRGRGGGBBBBYYYYRRRRGGGG

これを45度回転させた感じに塗ればよい。
x座標+y座標が奇数のマスと偶数のマスで色をちょっとずらしてやると安心。
以下のコードでは、例えばD=8のとき以下のような図を得られる。

BYGYGYGYRGYGYGYGBYGYG
RBYGYGYRBRGYGYGBRBYGY
BRBYGYRBRBRGYGBRBRBYG
RBRBYRBRBRBRGBRBRBRBY
BRBRYBRBRBRBGRBRBRBRY
RBRYGYBRBRBGYGRBRBRYG
BRYGYGYBRBGYGYGRBRYGY
RYGYGYGYBGYGYGYGRYGYG
RGYGYGYGBYGYGYGYRGYGY
BRGYGYGBRBYGYGYRBRGYG
RBRGYGBRBRBYGYRBRBRGY
BRBRGBRBRBRBYRBRBRBRG
RBRBGRBRBRBRYBRBRBRBG
BRBGYGRBRBRYGYBRBRBGY
RBGYGYGRBRYGYGYBRBGYG
BGYGYGYGRYGYGYGYBGYGY
BYGYGYGYRGYGYGYGBYGYG
RBYGYGYRBRGYGYGBRBYGY
BRBYGYRBRBRGYGBRBRBYG
RBRBYRBRBRBRGBRBRBRBY
BRBRYBRBRBRBGRBRBRBRY
int H,W,D;
int R[1001][1001];
string A="RYGB*";

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>H>>W>>D;
	
	if(D%2) {
		FOR(y,H) FOR(x,W) R[y][x]=(y+x)%2;
	}
	else if(D%4==2) {
		FOR(y,H) FOR(x,W) R[y][x]=(y%2*2)+(y/2+x/2)%2;
	}
	else {
		FOR(y,H) FOR(x,W) {
			int dy=y+x+1000;
			int dx=y-x+1000;
			R[y][x]=dy/D%2*2+dx/D%2;
			if((y+x)%2==1) R[y][x]^=3;
		}
		
	}
	
	
	FOR(y,H) {
		FOR(x,W) cout<<A[R[y][x]];
		cout<<endl;
	}
}

まとめ

かなり手こずった…。