TopCoderOpen 2019 Japan Regional : Easy RealWithRooks

MediumよりEasyの方が難しくない？
https://community.topcoder.com/stat?c=problem_statement&pm=15638&rd=17637

問題

H*Wの大きさのチェス盤に、白黒のルークを計N個置く。
この際互いに1手で取れる位置にあるルークの対を最大化せよ。

解法

置くルークの色は、グリッド位置のパリティで決めよう。
そうすると、あとはルークを左上に詰めておくようにすると、同じ列・行にn個のルークがある場合、(n-1)組の互いに取れる位置にある対ができる。

あとはできるだけ正方形に近くなるように配置していこう。

char A[55][55];

class RealWithRooks {
	public:
	vector <string> construct(int R, int C, int N) {
		vector<string> ret;
		int x,y,z;
		FOR(y,R) {
			string S(C,'.');
			ret.push_back(S);
		}
		
		FOR(z,100) {
			FOR(y,z) if(z<C&&y<R&&N) N--,ret[y][z]=((y+z)%2)?'B':'W';
			FOR(x,z) if(z<R&&x<C&&N) N--,ret[z][x]=((z+x)%2)?'B':'W';
			if(z<R&&z<C&&N) N--,ret[z][z]='W';
		}
		return ret;
	}
}

まとめ

最初は斜めに敷き詰めようとして失敗した。