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; } }