PEをMathematicaで

Project Eulerに挑戦してみよう

Project Euler 147 / 斜交平行格子内の長方形

3x2 の斜め線が引かれた格子には下図のように全部で37個の異なった長方形が存在する。

f:id:variee:20170728013418g:plain

3x2 より横にも縦にも小さい5個の格子(1x1,2x1,3x1,1x2,2x2)を考えると, それらに存在する長方形の数は以下のようになる。

  • 1x1: 1
  • 2x1: 4
  • 3x1: 8
  • 1x2: 4
  • 2x2: 18

これらに 3x2 の格子の37を加えると全部で72個の長方形が存在する。47x43 以下の格子について異なる長方形の数を求めよ。

Problem 147 - Project Euler


「解いた」のではなく,調べました。code golf にそっくりの問題があります。betseg 氏のコードと Neil,Sherlock9 両氏の解説を読めばわかるでしょう。

codegolf.stackexchange.com

m*n (m≧n) の格子を考えます。
傾いていない長方形は C[m+1, 2]*C[n+1, 2] 個。
傾いた長方形は n*n の部分と残りの部分にわけて数えます。
(n-1)n(4n^2+4n+3)/6 + (m-n)n(4n^2-1)/3 個。

これらの和をとります。