kmjp's blog

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

Codeforces #1030 : Div2 E. Grid Coloring

こちらのコードは短い。
https://codeforces.com/contest/2118/problem/E

問題

H*Wのグリッドを彩色したい。
毎回任意のマスに色を塗れるが、その際最も遠い彩色済みのマスにペナルティが1加算される。
ペナルティが4以上のマスが生じないようにマスを埋められるか。

解法

真ん中のマスから初めて、上下1行を追加→左右1行を追加、を交互に行っていこう。

int T,H,W;

void go(int y,int x) {
	if(y>=1&&y<=H&&x>=1&&x<=W) {
		cout<<y<<" "<<x<<endl;
	}
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>H>>W;
		
		vector<pair<int,int>> V;
		int cy=H/2+1,cx=W/2+1;
		go(cy,cx);
		for(i=1;i<=max(H,W);i++) {
			FOR(j,2*i-1) {
				int m=(j%2)?1:-1;
				go(cy+i,cx+m*(j+1)/2);
				go(cy-i,cx+m*(j+1)/2);
			}
			FOR(j,2*i-1) {
				int m=(j%2)?1:-1;
				go(cy+m*(j+1)/2,cx+i);
				go(cy+m*(j+1)/2,cx-i);
			}
			go(cy-i,cx-i);
			go(cy+i,cx-i);
			go(cy-i,cx+i);
			go(cy+i,cx+i);
		}
		cout<<endl;
		
	}
}

まとめ

結果だけ見ると単純だけど、本番中に詰めるのが難しい。