Project Eulerで初めて100番以内に入った
うれしい。
・Problem 476 - Project Euler
60th solver of Problem476 is matsulib from Japan.
— Project Euler (@projecteulerbot) June 15, 2014
Mapleで連立方程式を解いて出てきた数式をPyPyに突っ込んだだけ。実行時間は30分くらい。(後日改良してマルチコア化して4分)
僕のコードではPythonだと3時間待っても計算が終わらなかったけど、
他の人のコードだとPythonで30分、PyPyなら20秒で終わるからつらい。
でもまあProject Eulerはプロコンみたいな制限時間とかないしn=2000くらいなら
O(n^3)でもゴリ押しできるから頑張れば解けるって問題だった。
というかこれだよね。
・マルファッティの円 - Wikipedia
直感的には貪欲法で良さそうだけど正当性の証明とか高速化とかは分からない。