読者です 読者をやめる 読者になる 読者になる

PEをMathematicaで

Project Eulerに挑戦してみよう

Project Euler 91 / 整数座標における直角三角形

点 P(x1, y1) と点 Q(x2, y2) はともに格子点であり,原点 O(0,0) とあわせてΔOPQをなす。

各座標が 0 ≤ x1, y1, x2, y2 ≤ 2 をみたすとき,直角三角形は14個できる。

f:id:variee:20170502004446g:plain

0 ≤ x1, y1, x2, y2 ≤ 50 のとき,直角三角形は何個作れるか?

Problem 91 - Project Euler


計算量 O(n^4) をどう処理するかがポイントなのだろうと思います。残念ながらオーダーは落とせなかったので,係数を小さくする工夫をしました。

  • 三平方の定理のかわりに内積を使う
  • あらかじめ座標の範囲をしぼっておく

「y2 は y1 以上」が効いたように思います。何も工夫しないときと比べて候補の点が半分くらいに減ります。