CODE FESTIVAL 2018 Qual B : C - Special Cake for CODE FESTIVAL

始めたのが終了直前だったのでSubmitせず。Dまでは自力で行けそうだった。
https://beta.atcoder.jp/contests/code-festival-2018-qualb/tasks/code_festival_2018_qualb_c

問題

N*Nの白マスで構成されたグリッドが与えられる。
1マスを指定し、その上下左右の隣接マスを含む5マスを黒く塗る、ということを繰り返す。
同じマスが２回以上塗られてもよい。

指定回数201800以下でN*Nを黒く塗る例を答えよ。

解法

最大でN=1000でN*N/5=200000となるので、無駄は少なく重複のないよう効率的に塗らなければいけない。
指定するマスとマスの間はマンハッタン距離で３マス離すと、間が塗れる、ということに気付くと以下のような塗り方が思いつく。

..X....X....X
X....X....X..
...X....X....
.X....X....X.
....X....X...
..X....X....X

これだと端を一部塗り残す可能性があるが、残り1800マス指定する余地があるのでそれで塗ればよい。

int N;
int A[1010][1010];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	int num=0;
	FOR(y,N) FOR(x,N) if((2*x+y)%5==0) {
		A[y][x]|=3;
		num++;
		if(y) A[y-1][x]|=1;
		if(x) A[y][x-1]|=1;
		A[y+1][x]|=1;
		A[y][x+1]|=1;
	}
	
	FOR(y,N) {
		FOR(x,N) {
			if(A[y][x]==0) A[y][x]=3, num++;
			if(A[y][x]==3) cout<<"X";
			else cout<<".";
		}
		cout<<endl;
	}
	
}

まとめ

これは割とすんなり思いつけたね。