TopCoder SRM 507 Div1 Medium CubePacking

これもすんなり解けた。
http://community.topcoder.com/stat?c=problem_statement&pm=11266

問題

１辺１の立方体がNs個と、１辺Lの立方体がNb個ある。
これらを大きな直方体にすべて積み込みたい。
最小の体積の直方体を答えよ。

解法

全体でNs + Nb*(L^3)以上の体積が必要である。
よって、体積の初期値V=Ns + Nb*(L^3)から初めて、Vをインクリメントしながら立方体をすべて詰め込めるか試していけばよい。

体積Vが定まったとき立方体が全部詰め込めるかは、Vの約数から３辺の長さx,y,zの候補を列挙し、(x/L)*(y/L)*(z/L)>=Nbになるか試せばよい。

Lはさほど大きくないので、Vをインクリメントする回数は最大でもL^3==1000回程度であることが期待でき、十分間に合う。

vector<ll> enumdiv(ll n) {
	set<ll> S;
	for(ll i=2;i*i<=n;i++) if(n%i==0) S.insert(i),S.insert(n/i); 
	S.insert(n);
	return vector<ll>(S.begin(),S.end());
}

class CubePacking {
	public:
	int getMinimumVolume(int Ns, int Nb, int L) {
		ll S=Ns+L*L*L*Nb;
		int x,y,z;
		
		while(1) {
			vector<ll> V = enumdiv(S);
			
			FOR(x,V.size()) {
				if(V[x]>S/V[x]) break;
				for(y=x;y<V.size();y++) {
					if(V[y]>S/(V[x]*V[y])) break;
					
					if(S%(V[x]*V[y])==0 && (V[x]/L)*(V[y]/L)*(S/(V[x]*V[y])/L)>=Nb) 
						return (int)S;
				}
			}
			S++;
		}
	}
};

まとめ

Vの候補がさほど多くないことに気づけば貪欲法で解ける。