matsulibの日記

自分用メモ

Project Eulerで初めて100番以内に入った

うれしい。
Problem 476 - Project Euler

Maple連立方程式を解いて出てきた数式をPyPyに突っ込んだだけ。実行時間は30分くらい。(後日改良してマルチコア化して4分)
僕のコードではPythonだと3時間待っても計算が終わらなかったけど、
他の人のコードだとPythonで30分、PyPyなら20秒で終わるからつらい。
でもまあProject Eulerはプロコンみたいな制限時間とかないしn=2000くらいなら
O(n^3)でもゴリ押しできるから頑張れば解けるって問題だった。

というかこれだよね。
マルファッティの円 - Wikipedia
直感的には貪欲法で良さそうだけど正当性の証明とか高速化とかは分からない。