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

TopCoder SRM 507 Div1 Medium: CubePacking

解法

d.hatena.ne.jp
mayokoex.hatenablog.com

最低でもNs+Nb*L*L*Lは必要だが、L*L*Lを1列にNb個積み上げて、そこに1*1*1のNs個を出来るだけ平たく詰めば条件を満たす直方体が作れる。あとは、体積について総当りして体積の各辺について総当りすれば良い。

コード

public class CubePacking {

	public int getMinimumVolume(int Ns, int Nb, int L) {
		int V = Ns + Nb * L * L * L;
		int maxH = (Ns + L * L - 1) / (L * L);
		int maxV = (maxH + Nb * L) * L * L;
		for (int v = V; v <= maxV; v++) {
			// 体積vとなる直方体の辺a,b,cの長さを考える
			for (int a = 1; a <= Math.sqrt(v); a++) {
				if (v % a != 0) {
					continue;
				}
				int s = v / a;
				for (int b = 1; b <= Math.sqrt(s); b++) {
					if (s % b != 0) {
						continue;
					}
					int c = s / b;

					int na = a / L;
					int nb = b / L;
					int nc = c / L;
					if (na * nb * nc >= Nb) {
						// Nb個の大きい立方体が全て入り、かつ、最低体積以上なので、
						// 小さい立方体も全てはいるはず
						return v;
					}
				}
			}

		}
		return maxV;
	}
}