PEをMathematicaで

Project Eulerに挑戦してみよう

Project Euler 86 / 直方体のルート

下に示す直方体は寸法が 6×5×3 である。この直方体のある頂点Sにクモがいる。また,反対の頂点Fにはハエがいる。SからFまで壁に沿って移動する最短ルートは図に示す通りで,この長さは10である。

f:id:variee:20170521163206g:plain

最短ルートの候補は3本あるが,最短のものがいつも整数長さとは限らない。

M×M×M 以下の寸法の直方体について,最短ルートの長さが整数である直方体の数を考える。

M=100 のとき,条件をみたす直方体は2060個ある。この M=100 は,個数が2000を超える最小の M である。なお, M=99 のときは1975個である。

100万個を超える最小のMを求めよ。

Problem 86 - Project Euler

3辺の長さを a, b, c (a≦b≦c) とおきます。簡単な計算によって最短ルートの長さが

 \sqrt{(a+b)^2+c^2}

だとわかります。

これが整数になる条件を考えるわけですが,(a, b) をそのまま相手にすると O(n^2) の時間がかかってしまうので,a+b=x とおいて x → (a, b) の順に2段階に分けて数えます。

  1. x を求める
  2. 対応する (a, b) の個数を求める

(a, b) の個数は図の赤線部の格子点数です。受験数学でよくある「格子点を数える」系ですね。

f:id:variee:20170521174829p:plain