プロジェクトオイラー 問８６

プロジェクトオイラーの問題をpythonでやってみます。
日本語翻訳サイトは、プロジェクトオイラー日本語 でネット検索です。

問８６「直方体の道筋」
下に示す直方体は寸法が6×5×3である.
この直方体の1つの頂点Sにクモがいる. また反対の頂点Fにはハエがいる. 
SからFまでの壁に沿って直線移動する最短ルートは図に示す通りで, この長さは10である.

この最短ルートの候補は3本あるが, 最短のものがいつも整数長さとは限らない.
さて, M×M×M以下の寸法の直方体について, 最短ルートが整数である直方体の数を考える. 
M=100のとき, 条件を満たす直方体は2060個ある. このM=100は個数が2000を超える最小のMである. なお, M=99のときは1975個である.

100万個を超える最小のMを求めよ.





注意！！！
自力で解きたい人へ
以降の記述には解法に関するネタバレが含まれます。






私の回答例は以下の通りです。

def f(n):
	m = c = 0
	while c<=n:
		m += 1
		k, L = m*m, []
		for i in xrange(2, m*2+1):
			s = (i*i+k)**.5
			if s==int(s): L.append(i)
		if not L: continue
		for i in L:
			c += i/2
			if m<i: c -= (i-m-1)
	return m, c

n = 1000000
m, c = f(n)
print "M:", m
print "num of routes:", c

反対側の頂点までの最短ルートの候補は、展開図で考えると以下の３つです。
直方体の各辺の長さをa,b,cとして、
・直角を挟む２辺が「a」「bとcの和」の直角三角形の斜辺：a2+(b+c)2 = a2+b2+c2+2bc
・直角を挟む２辺が「b」「cとaの和」の直角三角形の斜辺：b2+(c+a)2 = a2+b2+c2+2ca
・直角を挟む２辺が「c」「aとbの和」の直角三角形の斜辺：c2+(a+b)2 = a2+b2+c2+2ab

a≦b≦cとすると、最短ルートをsとして以下のとおりです。
s2 = a2+b2+c2+2ab = (a+b)2+c2　・・・(A)

１．関数f(n)
・直方体のうち、各辺の長さと反対の頂点までの最短距離が整数長さのm×m×m以下の寸法で、その個数がn個を超える最小のmを返します。

・カウントすべき直方体の個数を変数cにカウントアップします。mとcはゼロクリアしておきます。

・whileループはカウントすべき直方体の個数cが限界値nを超えたら終了します。

・数え上げる直方体の最長辺がmなので式(A)は、a≦b≦c≦mという条件が付きます。最長辺の長さcをmとして、c2を変数kとします。

・for i in xrange(2, m*2+1):
　a+bの値を変数iとして1ずつ増やしていきます。
　この変数iの最小値はa=b=1のときで2、最大値はa=b=mのときなのでm*2です。
　xrange関数は第1引数から(第2引数-1)の値を第3引数（初期値1）刻みで発生させます。

・s = (i*i+k)**.5
　if s==int(s): L.append(i)
　式(A)を実装して、最短ルート長さsを求め、これをint関数で小数点以下切り捨てても同じ値かということで整数判定します。このsが整数ならばリストLにためます。

・if not L: continue
　上記ロジックでリストLが空の場合は整数長さの最短ルートがないので、現在のmでの探索は終了です。

・for i in L:
　c += i/2
　if m<i: c -= (i-m-1)
　これまでのロジックでリストLには題意に合うa+bの値をためていますので、1つずつ取り出して、a,bが整数になる組み合わせの個数を変数cに累計していきます。
　リストLから取り出した値iが２つの整数の和である組み合わせは、
　(1, i-1), (2, i-2), ..., (i-2, 2), (i-1, 1)
　の(i-1)通りで、真ん中以降は同じ組み合わせなので、異なる組み合わせとしては半分の(i-1)/2個です。i-1が奇数の場合は切り捨てます。

　リストLから取り出した変数iがm以下ならば、aとbの組み合わせは全部採用ですが、リストLには最大m*2までの値があるので、a,bの片方がmを超えてしまう分を差し引きます。

解答はこのすぐ下の行です。文字の色を白にしてます。選択状態にすると見えます。
M: 1818
num of routes: 1000457