Codeforces #917 : Div2 E. Construct Matrix

構築ゲーはなかなかに苦手。
https://codeforces.com/contest/1917/problem/E

問題

偶数Nと非負整数Kが与えられる。
01で構成されるN*Nの行列のうち、以下を満たすものを1つ構築せよ。

• 和がKである。
• 各行において、1の個数の偶奇が一致する
• 各列において、1の個数の偶奇が一致する

解法

Nが偶数なので、Kが2の倍数なのは必須。
うち、K=2またはN*N-2の場合は、N=2以外の場合は条件を満たせない。

まず、全部1で埋めたうえで2*2の領域を0にすれば、偶奇の条件に反することなく1を4つ減らせる。
問題はKが4で割って2で余る場合だが、これだけはしょうがないので4*4内で6個1を配置する方法を考えよう。

int T,N,K;
int A[1010][1010];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N>>K;
		FOR(y,N) FOR(x,N) A[y][x]=0;
		
		if(K%2) {
			cout<<"No"<<endl;
			continue;
		}
		if(K==2||K==N*N-2) {
			if(N==2) {
				cout<<"Yes"<<endl;
				cout<<"1 0"<<endl;
				cout<<"0 1"<<endl;
			}
			else {
				cout<<"No"<<endl;
			}
			continue;
		}
		int skip=0;
		if(K%4==2) {
			A[0][1]=A[0][2]=A[1][0]=A[1][2]=A[2][0]=A[2][1]=1;
			K-=6;
			if(K) {
				A[0][0]=A[3][3]=A[0][3]=A[3][0]=1;
				K-=4;
			}
			skip=1;
		}
		FOR(y,N/2) FOR(x,N/2) if(K) {
			if(skip&&y<=1&&x<=1) continue;
			A[y*2][x*2]=A[y*2][x*2+1]=A[y*2+1][x*2]=A[y*2+1][x*2+1]=1;
			K-=4;
		}
		cout<<"Yes"<<endl;
		FOR(y,N) {
			FOR(x,N) cout<<A[y][x]<<" ";
			cout<<endl;
		}
		
		
	}
}

まとめ

4*4に6個または10個1を配置する方法に気付けるかどうか。