CODE FESTIVAL 2016 Relay : J - 連結チェスボード / Connected Checkerboard

これもIより簡単？
http://cf16-relay-open.contest.atcoder.jp/tasks/relay_j

問題

白黒市松模様上に塗られたN*Nのグリッドがある。
一部の白マスを黒く塗り、全黒マスが辺を共有する隣接セルをつなげた時連結するようにしたい。
黒く塗るマスの候補を答えよ。ただし170,000個以下でなければならない。

解法

Nの上限1000のケースを考えると、黒く塗れるマスの上限170,000はグリッドのセル数の約1/6である。
そこで1/6のマスを塗ることを考えよう。

とはいえあまり複雑なことは必要なく、

• 最左列は全マス黒にする
• 最上段をはじめ、3行毎に全部黒にする
• 加えて最下段も黒にする

でよい。
大体3行毎にN/2個の白マスを黒く塗るので、全体の1/6ぐらい黒く塗ることになる。

int N;
string S[1010];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(y,N) {
		FOR(x,N) S[y]+="#."[(x+y)&1];
	}
	
	int ret=0;
	FOR(y,N) if(S[y][0]=='.') S[y][0]='*', ret++;
	FOR(x,N) if(S[N-1][x]=='.') S[N-1][x]='*', ret++;
	for(y=1;y<N;y+=3) {
		for(x=1;x<N;x++) if(S[y][x]=='.') S[y][x]='*', ret++;
	}
	
	_P("%d\n",ret);
	FOR(y,N) FOR(x,N) if(S[y][x]=='*') _P("%d %d\n",x,y);
}

まとめ

先こっちやればよかった。