kmjp's blog

競技プログラミング参加記です

yukicoder : No.883 ぬりえ

古い問題で記事書いてないものを書いておく。
https://yukicoder.me/problems/no/883

問題

整数N,Kが与えられる。
ある正方形形状のグリッドに対し、Nマスを黒く、残りを白く塗りたい。
その際、各行・各列黒マスはK個以下となるようにしたい。

最小のグリッドサイズと、塗り方の一例を示せ。

解法

グリッドの1辺のサイズをLとすると、L*min(L,K)がN以上なら解がある。
あとは実際に構築すればよくて、(0-originで)r行目にはr列目から(r+K-1)%K列目までを塗るようにすれば、「各行・各列黒マスはK個以下となる」を満たしてL*min(L,K)個のマスを黒く塗ることができる。

int N,K;
int T;
string S;

void solve() {
	int i,j,k,l,r,x,y; string s;

	cin>>N>>K;
	int NT=N;
	FOR(i,1010) if(i*min(i,K)>=N) {
		cout<<i<<endl;
		FOR(y,i) {
			string S(i,'.');
			FOR(x,min(i,K)) if(NT) {
				S[(x+y)%i]='#';
				NT--;
			}
			cout<<S<<endl;
		}
		break;
	}
	
}

まとめ

なんでこれ記事書いてないんだろ。
難易度改定があった問題かな?