Aはしんどかった。
http://code-festival-2017-quala.contest.atcoder.jp/tasks/code_festival_2017_quala_d
問題
H*Wのグリッドがある。
各マスを４色のいずれかで塗ることを考える。
マンハッタン距離が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; } }
まとめ
かなり手こずった…。
