Codeforces #783 : Div1 C. Half Queen Cover

BとC同じくらいの時間で解いてる。
https://codeforces.com/contest/1667/problem/C

問題

チェスにおけるHalf Queenとは、上・下・左・右・左上45度・右下45度の6方向の向きに、何マスでも移動できるものとする。

整数Nが与えられる。N*Nのチェスの盤面に、いくつかHalf Queenを置き、どのマスも1個以上のHalf Queenで1手以内となるようにしたい。
最小何個の駒を置けばよいか、配置例とともに答えよ。

解法

Nが3の倍数の時、2/3*N個のHalf Queenで覆うことができる。そうでない場合、floor(2/3*N)+1個で覆える。
前者の場合、盤面をN/3ずつ分け3*3の領域に分けたとする。
左上の領域の反対角に相当するマスと、真ん中の領域の反対角に相当するマス(を1マスずらしたもの)にN/3個ずつ駒を置いていくとよい。

int N;

void check(int N,vector<pair<int,int>> V) {
	int MP[N][N]={};
	
	FORR2(y,x,V) {
		int i;
		FOR(i,N) MP[y][i]=MP[i][x]=1;
		FOR(i,N) {
			int y2=y+i-x;
			if(y2>=0&&y2<N) MP[y2][i]=1;
		}
	}
	FORR2(y,x,V) MP[y][x]=2;
	int i,j;
	
	FOR(i,N) {
		FOR(j,N) cout<<MP[i][j];
		cout<<endl;
	}
	
	FOR(i,N) FOR(j,N) assert(MP[i][j]);
	
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	
	vector<pair<int,int>> V;
	if(N%3==0) {
		FOR(i,N/3) V.push_back({N/3-1-i,i});
		FOR(i,N/3) V.push_back({(N/3-1)*2-i,N/3+i});
	}
	else {
		FOR(i,N/3+1) V.push_back({N/3-i,i});
		FOR(i,N/3) V.push_back({(N/3)*2-i,N/3+1+i});
	}
	
	//check(N,V);
	cout<<V.size()<<endl;
	FORR2(y,x,V) cout<<y+1<<" "<<x+1<<endl;
	
}

まとめ

本番証明まではせず実験で傾向を見て解いてしまったな…。