SRM 507 500pt: CubePacking

keyword

全探索　C++

問題概要

1辺1の立方体がS個あり、1辺L(<10)の立方体がB個ある。これらを全部詰めるのに最小でどれだけの体積の直方体があれば大丈夫か求める問題。

解法

全部の体積をVとすると答えの範囲は下限がV, 上限がV+L*L-1。この上限はBを一列に並べたものから分かる。区間の幅がL*Lしかないので答えに関して全探索する。答えを決め打ちしてやると、直方体の3辺の候補はそんなに多くないのでこれも全部調べられる。直方体の3辺を決めたとき大丈夫かどうかはGreedyっぽく考えて定数時間で判定できる。

感想（補足）

計算量について考えてみるとO(L*L*sqrt(V+L*L)*f(cbrt(V+L*L)))。ただしf(V)はV以下の数に約数が平均幾つあるか。約数の個数d(n)は何に漸近するのかよく知らない。感覚的にはlogくらいだけど。M(n) = max_{1

class CubePacking {
public:
int getMinimumVolume(int S, int B, int L) {
	int Q = L*L*L;
	for(int add = 0; add < L*L; add++){
		int xyz = Q*B + S + add;
		for(int i=L; i*i*i<=xyz; i++)if(xyz%i==0){
			for(int j=i, yz=xyz/i; j*j<=yz; j++)if(yz%j==0){
				int as[3] = {i,j,yz/j};
				do{
					if(check(S,B,L,as[0],as[1],as[2])) return xyz;
				}while(next_permutation(as,as+3));
			}
		}
	}
	return -1;
}

bool check(int S, int B, int L, int x, int y, int z){
	int nxy = (x/L) * (y/L);
	int nz = (B+nxy-1)/nxy;
	return nz*L <= z;
}