読者です 読者をやめる 読者になる 読者になる

kmjp's blog

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

TopCoder SRM 507 Div1 Medium CubePacking

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

問題

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

解法

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

体積Vが定まったとき立方体が全部詰め込めるかは、Vの約数から3辺の長さ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の候補がさほど多くないことに気づけば貪欲法で解ける。

広告を非表示にする