のてすきあ − 完全独習非プログラマー −

Haskell で Project Euler を解く素人遊び

Problem 75

周の長さが12で、各辺の長さが全て整数の直角三角形は(3,4,5)だけである。
同様に24 -> (6,8,10), 30 -> (5,12,13) 等々、長さを与えれば3辺の長さが決まる。
中には120 -> (30,40,50), (20,48,52), (24,45,51) のように、ある周長に対して複数の直角三角形が存在する場合もある。

周長が1,500,000までの直角三角形のうち、3辺の長さが1通りしかないものはいくつあるか。


 さて、解法の説明が難しい。全探索が上手くいかないことは容易に想像が付く。何かしらの方法で効率的に探索しなければならない。今回は割と事前の手計算が必要だった。  問題が円と直線が格子点で交わることの言い換えであると気付けば、なんとなく道が見えてくる。

X^{2} + Y^{2} = Z^{2}
X + Y = L - Z

をX,Yの連立方程式だと見て、与えられたLに対してX,Yがともに整数になるZが1つしかないような(L,Z)を探せば良いと分かる。それをナイーブに実装したのが以下である。


 省ける計算がある。それは相似の三角形に対する評価である。例えば問題文に登場する周長120の直角三角形は3辺の組み合わせが複数ある。ということは、周長が120の倍数の直角三角形は、全て複数の組み合わせを持つことが調べなくても分かる。

 なので題意を満たさない小さな三角形が見つかった時には、その相似形を評価対象から省くことで高速化を図った。しかし結論を言ってしまうと、計算時間が5分→4分程度の短縮にしかならなかった。

 1番目の方法で計算時間が掛かる本質は、1つの周長Lに対して、ある範囲の斜辺の長さを全てチェックしていること、言い換えれば計算量がO(N2)であることにある。相似形の評価を省いたところで、基本的な評価方法は変わらず、計算量がO(N2)であることも変わりはないので、劇的な短縮にならないのはある意味当然なのかも知れない。

早くならない…★