体積から考える直方体の組み合わせ

体積から考える直方体の組み合わせ

締め切りが 2017/12/12 10:00 AM なので，その 1 分後に投稿されるように予約

いずれの辺の長さも整数である3つの直方体を考えます。

その直方体の体積の和が与えられたとき、考えられる直方体の組み合わせが何通りあるかを求めてください。
（縦、横、高さを入れ替えたものは一つとカウントします。また、直方体の順番を入れ替えたものも一つとカウントします。）

例えば、体積の和が10のとき、直方体の縦,横,高さは以下の16パターンがあります。

No　一つ目の直方体　二つ目の直方体　三つ目の直方体
 1　1, 1, 1　　1, 1, 1　　1, 1, 8
 2　1, 1, 1　　1, 1, 1　　1, 2, 4
 3　1, 1, 1　　1, 1, 1　　2, 2, 2
 4　1, 1, 1　　1, 1, 2　　1, 1, 7
 5　1, 1, 1　　1, 1, 3　　1, 1, 6
 6　1, 1, 1　　1, 1, 3　　1, 2, 3
 7　1, 1, 1　　1, 1, 4　　1, 1, 5
 8　1, 1, 1　　1, 2, 2　　1, 1, 5
 9　1, 1, 2　　1, 1, 2　　1, 1, 6
10　1, 1, 2　　1, 1, 2　　1, 2, 3
11　1, 1, 2　　1, 1, 3　　1, 1, 5
12　1, 1, 2　　1, 1, 4　　1, 1, 4
13　1, 1, 2　　1, 1, 4　　1, 2, 2
14　1, 1, 2　　1, 2, 2　　1, 2, 2
15　1, 1, 3　　1, 1, 3　　1, 1, 4
16　1, 1, 3　　1, 1, 3　　1, 2, 2
標準入力から体積の和が与えられるとき、直方体の組み合わせの数を標準出力に出力してください。
なお、体積の和は300以下の整数とします。

【入出力サンプル】
標準入力
10

標準出力
16

======================================================================

R でも結構いいところまで行くが，Java には勝てない

ag = integer(300)

g = function(v) {
  count = 0
  for (i1 in 1:ceiling(v ^ (1 / 3))) {
    for (i2 in i1:v) {
      if (i1 * i2 > v) {
        break
      }
      i3 = v / (i1 * i2)
      if (i3 < i2) {
        break
      } else if (i3 == floor(i3)) {
        count = count + 1
        ag[count] = (i1 * 1000 + i2) * 1000 + i3
      }
    }
  }
  ag[1:count]
}

tbl = vector("list", 300)
for (i in 1:300) {
  tbl[[i]] = g(i)
}

f = function(v) {
  ah = matrix(0, 3000, 3)
  count = 0
  for (i1 in 1:ceiling(v / 3)) {
    lst1 = tbl[[i1]]
    for (i2 in i1:v) {
      if (i1 + i2 > v) {
        break
      }
      i3 = v - i1 - i2
      if (i3 < i2) {
        break
      }
      lst2 = tbl[[i2]]
      lst3 = tbl[[i3]]
      l1 = length(lst1)
      l2 = length(lst2)
      l3 = length(lst3)
      count2 = 0
      for (j1 in 1:l1) {
        for (j2 in 1:l2) {
          for (j3 in 1:l3) {
            mx = max(lst1[j1], lst2[j2], lst3[j3])
            mn = min(lst1[j1], lst2[j2], lst3[j3])
            me = lst1[j1] + lst2[j2] + lst3[j3] - mx - mn
            count2 = count2 + 1
            ah[count2, ] = c(mn, me, mx)
          }
        }
      }
      count = count + nrow(unique(ah[1:count2, , drop = FALSE]))
    }
  }
  cat(count)
}

# f(scan(file("stdin", "r")))

system.time(f(9)) # 11
system.time(f(10)) # 16
system.time(f(20)) # 133
system.time(f(64)) # 4563
system.time(f(100)) # 17251
system.time(f(300)) # 438379