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

Problem 39

Problem 39
うっかり見落としてしまいそうでしたが、
上記リンク先の日本語訳Wikiと原文で
内容が若干異なりましたので、
念のため原文へのリンクも張っておきます。
Problem 39の原文

辺の長さが{a,b,c}と整数の3つ組である直角三角形を考え,
その周囲の長さをpとする.
p = 120のときには3つの解が存在する:

{20,48,52}, {24,45,51}, {30,40,50}
p ≦ 1000 で解の数が最大になる p を求めよ.


a < b < c としても一般性を損なわないので、

a**2 + b**2 == c**2    ---- (1)
1 < a < b < c    ---- (2)
p = a + b + c ≦ 1000    ---- (3)

が全て常に真であるとして話を進めます。


サクッと実装してしまいます。
最近、頭を捻らなくて済む問題が続いてしまっていますね。
でもめげずに面白い問題に出会えるまで続けます。

_N = 1000
_TOL = 0.001

counter = [0] * (_N + 1)
for a in xrange(1, _N + 1):
    for b in xrange(a + 1, _N + 1 - a):
        c = int((a ** 2 + b ** 2) ** 0.5 + _TOL)
        if a ** 2 + b ** 2 != c ** 2:
            continue
        if _N < a + b + c:
            continue
        counter[a + b + c] += 1
print counter.index(max(counter))

実行時間 0.609 [sec] で答え 840 が求まりました。


久々にトレランス(誤差)を気にしたコードを書きましたw
前職のCAD業界が少し懐かしい、春めく夜なのでした。