yukicoder : No.3378 Go Board

なるほど…。
https://yukicoder.me/problems/no/3378

問題

整数N,Kが与えられる。
以下を満たすようN*Nのグリッドを白黒で塗り分けられるか。可能なら一例を示せ。

• 黒マスはK個である。
• 黒マスに接する白マスもK個である。
• 黒マスは連結している。

解法

• N=2の時、K=2の時のみ解がある。
• N≧3の場合、
  • 3≦K≦Nの場合、１行目に左から(K-1)マス、2行目に一番左のマスだけ黒くすると良い。
  • N＜K≦N^2/2の場合
    • row-major orderで上から2Kマスを確保し、そこのうちKマスを黒く塗ることを考える。
    • まず2Kマスのうち各列最下段は黒く塗る。最下段に段差があるなら、そこを埋めるように塗る。
    • 次に、(2Kマスのうち)３列ごとに白マスを黒くする。これで各白マスは黒マスと接する状態になる。
    • まだ黒マスを置く必要があれな、白マスを適用に埋める。
• それ以外の場合解なし。

int T,N,K;
string S[505];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N>>K;
		FOR(y,N) S[y]=string(N,'.');
		
		if(N==2) {
			if(K==2) {
				cout<<"Yes"<<endl;
				cout<<"##"<<endl;
				cout<<".."<<endl;
			}
			else {
				cout<<"No"<<endl;
			}
		}
		else {
			if(K<=2||2*K>N*N) {
				cout<<"No"<<endl;
				continue;
			}
			
			if(K<=N) {
				FOR(x,K-1) S[0][x]='#';
				S[1][0]='#';
			}
			else {
				FOR(y,N) FOR(x,N) {
					if(y*N+x+1<=2*K-2*N) S[y][x]='?';
					else if(y*N+x+1<=2*K-N) S[y][x]='#';
				}
				int lef=K-N;
				FOR(y,N-1) FOR(x,N-1) {
					if(S[y][x]=='?'&&S[y+1][x]=='#'&&S[y][x+1]=='#') {
						S[y][x]='#';
						lef--;
					}
				}
				FOR(x,N) {
					if(x!=N-2&&x%3!=1) continue;
					FOR(y,N) {
						if(S[y][x]=='?'&&lef>0) {
							lef--;
							S[y][x]='#';
						}
						else {
							break;
						}
					}
				}
				FOR(y,N) FOR(x,N) if(S[y][x]=='?') {
					if(lef) {
						lef--, S[y][x]='#';
					}
					else {
						S[y][x]='.';
					}
				}
				
			}
			cout<<"Yes"<<endl;
			FOR(y,N) cout<<S[y]<<endl;

		}
		
	}
		
		
		
}

まとめ

場合分けが若干めんどい。