Codeforces #843 : Div2 F. Laboratory on Pluto

変わった入力形式の問題。
https://codeforces.com/contest/1775/problem/F

問題

整数Nが与えられる。
N個のマス目をくっ付けた図形を作りたいが、その際周囲のサイズを最小化したい。

そのような図形の一例を示せ。
また複数の形状がある場合は何通りあるか示せ。

解法

周囲を短くしたいので、凸図形となるようにしたい。
その際凸図形を囲う矩形のサイズがH*Wの場合、周囲のサイズは2*(H+W)となる。
よって、Hを総当たりしながら最小となるWを求めれば、周囲のサイズのサイズを求められる。

そこから四つ角で計H*W-N個だけマスを取り除くことを考える。
これは事前に前処理で計算することで、各角で取り除くマスの個数に対する組み合わせを求めておけば良い。

int T,U;
ll mo;
int N;
ll part[2020][2020];
ll from[2020],to[2020];

ll hoge(int H,int W,int N) {
	return from[H*W-N];
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	
	
	cin>>T>>U;
	if(U==2) {
		cin>>mo;
	
		part[0][1]=1;
		for(i=1;i<=2000;i++) {
			part[i][i]=1;
			for(j=i-1;j>=1;j--) {
				part[i][j]=(part[i][j+1]+part[i-j][j])%mo;
			}
		}
		from[0]=1;
		FOR(i,4) {
			ZERO(to);
			FOR(x,2000) for(y=0;x+y<=2000;y++) (to[x+y]+=from[x]*part[y][1])%=mo;
			swap(from,to);
		}
	}
	
	
	while(T--) {
		cin>>N;
		
		if(U==1) {
			int BH=101010,BW=101010;
			for(x=1;x<=1000;x++) {
				y=(N+(x-1))/x;
				if(x+y<BH+BW) BH=x,BW=y;
			}
			
			cout<<BH<<" "<<BW<<endl;
			FOR(y,BH) {
				FOR(x,BW) {
					if(N) {
						N--;
						cout<<"#";
					}
					else {
						cout<<".";
					}
				}
				cout<<endl;
			}
		}
		else {
			int BH=101010,BW=101010;
			for(x=1;x<=1000;x++) {
				y=(N+(x-1))/x;
				if(x+y<BH+BW) BH=x,BW=y;
			}
			ll ret=0;
			for(x=1;x<=1000;x++) {
				y=(N+(x-1))/x;
				if(x+y==BH+BW) ret+=hoge(x,y,N);
			}
			cout<<(BH+BW)*2<<" "<<ret%mo<<endl;
		}
		
		
	}
}

まとめ

そこまで難しくはない問題。