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

PEをMathematicaで

Project Eulerに挑戦してみよう

Project Euler 85 / 長方形の数え上げ

注意深く数えると横が3,縦が2の長方形の格子には18個の長方形が含まれている。

f:id:variee:20170416030959g:plain

ぴったり2,000,000個の長方形を含むような長方形の格子は存在しない。一番近い解を持つような格子の面積を求めよ。

Problem 85 - Project Euler


いろいろ考えた結果,問題27の類題(記事の最後にリンク貼っておきます)だときづきました。

  • 問題27:ある量の最大値を与える(a, b)の積を求める
  • 問題85:ある量の最小値を与える(m, n)の積を求める

解答をはじめます。縦 m,横 n(m≦n)の長方形の切り分け方は二項係数であらわせて,C[m,2]*C[n,2] 通りです。
m=n の場合を考えると m の最大値がわかり,m=2 の場合を考えると n の最大値がわかります。


あとは問題27とほぼ同じで,C[m,2]*C[n,2] と 2*10^6 の差でソートして最小値を与える組を取り出します。m, n の範囲をしぼりこむまでもなく0.2秒で終わりました。


variee.hatenadiary.com