Forum読んだ結果程度までは計算量減らせた。一発で答えの出る公式も書いてあるんだけどどうやって導出してんのか分からない…。
あまり詳しく言うと面白みがなくなるので要点だけ書くと、
- 斜めの長方形は正方形に内接している
- 正方形の個数を数え上げればよい
- 正方形に内接する長方形の個数は、辺の上にある交点の個数と同じ
- 正方形は辺の長さが整数か、整数+0.5かで数え方が違う
- 辺の長さが整数の正方形については頂点のx座標、y座標それぞれが整数、整数+0.5の場合で数え方が違う(つまり4パターンある)
例えば辺の長さがiの正方形で、頂点の座標値がxとyともに整数の場合、w*hの格子内には(w - i + 1)(h - i + 1)個の正方形が入る。
各正方形内には(i - 1)個の長方形が内接する(つまり正方形の1辺の上には交点がi-1個ある)。
よって長方形の個数は
よくわからんのでmaxima使って整理すると、
と、このような導出を他の正方形のパターンに対しても行って和を計算すればw*hの格子内に含まれる長方形の個数を計算する公式が得られる。このときついでに縦横の長方形を数える式も入れてしまえば良い。
それでもうちょっと頑張るとw * h以下の全ての格子についての和を求められるらしいんだけどもうmaximaにどう入力したらいいのかもよく分からないのでパス。それに下のコードでも1秒切れるので。
rect <- function(w, h){ if(h > w){ tmp <- h h <- w w <- tmp } ((3*h^2 + 3*h)*w^2 + (16*h^3 + 3*h^2 - h)*w - 8*h^4 + 2*h^2 - 6*h)/12 } ans <- 0 for(h in 1:47){ for(w in 1:43){ ans <- ans + rect(w, h) } } ans
