【Project Euler】Problem 86: 直方体の最短経路

• 本記事はProjectEulerの「100番以下の問題の説明は記載可能」という規定に基づいて回答のヒントが書かれていますので、自分である程度考えてみてから読まれることをお勧めします。

問題 86.直方体の最短経路

原文 Problem 86: Cuboid route

問題の要約：最大値Mの3辺が整数の直方体で、頂点SからFへ壁を伝って行く最短経路の長さがやはり整数になる場合が何通りあるか数える。その数が初めて$10^6$を超えるような最小のMを求めよ

• 例として初めて2000通りを超えるMは100。　M=99の時は1975通り

以下のステップで考えて行きます。

• 3辺$a \le b \le c \le M$とする。例題では$(a,b,c) = (3,5,6)$
• 直角三角形の底辺として$c$をカウントアップして行き、高さは$a+b$を$2c$までループする
• このとき斜辺$\sqrt{(a+b)^2+c^2}$が最短経路になりこれが整数となる場合が解の候補
• $a+b$の$a \le b \le c$の条件で$a$と$b$の取りえる値を数える、$(a+b)$と$c$の大小関係で以下のように変わってきます。

これをプログラムにしたのがこちら。

import itertools
# a<=b<=c<=M
count = 0
for c in itertools.count(3):
  for ab in range(3,2*c+1):
    rt = (ab**2 + c**2)**(1/2)
    if rt == int(rt):
      count += ab // 2 if (ab <= c) else (2*(c+1) - ab)//2
  if count > 10**6:
    print(f"Answer: {c},  count={count}")
    break

（開発環境：Google Colab）