Project Euler 147

プロジェクトオイラー
http://projecteuler.net/index.php

Q147.
47×43の長方形の中に、それに平行あるいは45度傾いた長方形を置く。そのような長方形の数と、元の47×43の長方形が収まる平行な長方形に収まる長方形の数の和。

辺の長さをM,Nとすると、
平行な長方形の数は簡単で、

M(M+1)(M+2)N(N+1)(N+2)/36

斜めの長方形は次のように考える。
M×Nの長方形の中の点を考える。これを最も右とする長方形を数える。このとき、その長方形が占める元の長方形に平行な長方形の数を数えて、その分だけ足していく。



M = 47
N = 43

counter = 0
for x in range(2, M * 2 + 1):
if x % 2 == 0:
start_y = 2
else:
start_y = 1
for y in range(start_y, N * 2, 2):
for u in range(2, min(x, N * 2) + 1):
for s in range(1, min(u, y + 1)):
t = u - s
if t > N * 2 - y:
continue
y_max = y + t
counter += (M - (x - 1) / 2) * (N - (y + t - 1) / 2)

counter += M * (M + 1) * (M + 2) * N * (N + 1) * (N + 2) / 36
print counter