UnKoder #05 : N-tuple Reach

N,Mが3以上なのがやさしさ。
https://www.hackerrank.com/contests/unkoder-05/challenges/n-tuple-reach

問題

N,M,Kが与えられる。

N*Mのグリッドの各セルを埋めるか空けるかして、各行・各列のうちリーチ(行・列全体のうち1マス以外埋まっている状態)となる箇所がK個となるものを答えよ。

解法

K==1の時は、以下のパーツを含め、その他のセルをすべて埋めればよい。

...
..#
###

• Kがmin(N,M)*2以下で偶数の場合、K/2個空きマスを並べればよい。
• それ以外の場合、以下の感じで斜めに空きマスを並べた後横か縦の長い方に沿って空きマスを配置すればよい。
  • N==Mの時はK=N+M-1、N!=Mの時はK=N+Mのケースを作れないので注意。

.########
#.#######
##.######
###.#####
####...##

int N,M,K;

string S[50];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M>>K;
	k=K;
	FOR(y,N) FOR(x,M) S[y]+="#";
	if(K==N+M-(N==M)) return _P("Impossible\n");
	
	if(K==1) {
		S[0][0]=S[0][1]=S[1][0]=S[1][1]=S[2][0]='.';
	}
	else if(K<=min(N,M)*2-(N!=M) && K) {
		FOR(y,K/2) S[y][y]='.';
		if(K!=N+M) {
			if(N>=M) S[K/2][K/2-1]='.';
			else S[K/2-1][K/2]='.';
			if(K%2) {
				if(N>=M) S[K/2+1][K/2-1]='.';
				else S[K/2-1][K/2+1]='.';
			}
		}
	}
	else if(K) {
		FOR(i,max(N,M)) {
			if(K<=0) continue;
			if(i<min(N,M)-1) S[i][i]='.', K-=2;
			else S[min(i,N-1)][min(i,M-1)]='.', K-=1;
		}
	}
	
	FOR(y,N) cout<<S[y]<<endl;
}

まとめ

どうすれば簡単に書けるんだろうな。