Project Euler 147

http://projecteuler.net/index.php?section=problems&id=147

水平の長方形の個数の計算は電卓レベルなので、斜めの長方形について考えます。
この問題はよく考えると、同じ長方形がいくつあるかという数え方と、点を固定してそれを頂点とする長方形はいくつあるかというのがあります。例題は前者で考えているので、恐らく後者で考えるのが近道でしょう。
斜めの長方形の上の頂点を固定して、高さが一定の長方形の個数を数えます。そしてついでにその頂点を横に動かしたときの個数の和を考えます。そうしたら、今度はその頂点を上下に動かします。同じ高さの長方形の個数は上下しても同じ、あるいは0なので、簡単に数えられます。ここで、頂点の座標は整数同士か半整数同士です。これらは分けて考えなければなりません。それをxで表しています。また、座標はコーディングしやすいように2倍して整数化しています。
本当はさらに式の計算を進めるともっと計算量が少なくて済むのかもしれませんが、このコードでも恐らく1秒以内で十分です。

def num_rectangles_h(x, h, X, Y):
	N = min(h - 1, 2 * X - h + 1)
	L = X - 1 if x % 2 == 0 else X
	S = 2 if x % 2 == 0 else 1
	L1 = (N - S) / 2 + 1
	if L >= L1 * 2:
		return 2 * L1 * (S + L1 - 1) + (L - L1 * 2) * N
	else:
		return (L - 1) * (L - 1) / 2 + S * L

def num_rectangles(X, Y):
	if X < Y:
		X, Y = Y, X
	
	def num_h(x, h):
		if x == 0:
			return (Y * 2 - h + 2) / 2
		else:
			return (Y * 2 - h + 1) / 2
	
	s = 0
	for x in range(2):
		for h in xrange(2, Y * 2 - x + 1):
			s += num_rectangles_h(x, h, X, Y) * num_h(x, h)
	return s + X * (X + 1) * Y * (Y + 1) / 4

N = 47
M = 43
print sum(num_rectangles(X, Y) for X in range(1, N + 1)
							   for Y in range(1, M + 1))