プロジェクトオイラー
http://projecteuler.net/index.php
Q126.
立方体のブロックを直方体状に並べる。そのブロックを最低限覆うようにブロックを並べたときのブロックの増分、さらにそのブロックを覆うようにブロックを並べたときの増分、...を考える。この増分をnとして、直方体を色々変えたときnが現れるパターン数をC(n)としたとき、C(n)=1000となる最も小さいn
最初、mapで3次元空間を実現してブロック一つずつ積み重ねるプログラムを書いたが、遅すぎて話にならなかった。しかたがないので、C++で書きかけていたら、アルゴリズムを思いついた。
例の3*2*1の場合を考える。3*2の層を考える。その層は、次は(3+2)*2増える。その次は、(3+2)*2+4増える。その次は、(3+2)*2+4*2増える。というようになる。その上の層は、さきほどの層の一つ遅れになる。その上はさらに遅れる。というようになる。そうすると簡単に計算できる。
C(n)を考えるのに、最初のステップでn個増すようなブロックの配置を考えればよい。最初の増分が小さい順にブロックの配置を生成していけばよいが、それは難しい。直方体の長さをa≥b≥cとして、最初の増分は(ab+bc+ca)となるが、簡易的にa(b+c)+bcでbcは小さいと考え、a(b+c) = n-1となるようなa,b,cを考える。すなわち、n-1の約数を生成して、ブロックの配置を生成していく。
from itertools import countdef gen_primes():
yield 2
yield 3
n = 3
while True:
n += 2
p = 3
while True:
if p * p > n:
yield n
break
if n % p == 0:
break
p += 2def gen_divisor(n):
if n == 1:
yield 1
else:
for p in gen_primes():
if n % p == 0:
e = 1
m = n
m /= p
while m % p == 0:
e += 1
m /= p
for q in gen_divisor(m):
r = 1
for i in range(e + 1):
yield r * q
r *= p
breakdef gen_cuboid(n):
n -= 1
for a in gen_divisor(n):
if a ** 3 < n or a * 2 > n:
continue
m = n / a
for b in range( (m + 1) / 2, min(m, a + 1)):
c = m - b
yield (a, b, c)def calc_C(c, n, C):
a = c[0] * c[1]
for i in count():
b = a + (c[0] + c[1]) * 2 + i * 4;
m = c[2] * (b - a) + a * 2
if m > n:
break
C[m] += 1
a = bdef calc(n):
C = [ 0 ] * (n + 1)
for m in xrange(2, n + 1):
for c in gen_cuboid(m):
calc_C(c, n, C)
return CN = 1000
n = 1000
while True:
print n
C = calc(n)
for i in xrange(len(C)):
if C[i] == N:
print i
exit(0)
n *= 2
