Project Euler 492

http://projecteuler.net/index.php?section=problems&id=492

62着。
日曜日考えていたが、全然わからない。とりあえずナイーブなコードから少し工夫しただけのものを書いて動かしてみたら、30日くらいかかりそうだった。並列にできるし、メモリも使わないから、4コアを使えば1週間くらい、PyhtonをC++に書き直せば1日くらいになるかもしれない。
月曜日の行き帰りに考えてみたが、何も思いつかなかった。しょうがないので帰ってからC++に書き直してみた。PyPyより6倍しか速くならなかった。それでも、4コアでごり押ししてみた。その間に適当なキーワードで検索してみたが、それらしいものは出てこなかった。
火曜日、ごり押ししているにもかかわらず、出かけてるときに休止モードにしてしまった。意味が無い。行き帰りに考えてみたが、やっぱり何も思いつかなかった。帰ってからまたいろいろ検索してみると、似たようなものが出てきた。これはいけるかもしれない。
水曜日、行きの電車の中で計算してみたら、ほぼわかった。帰りの電車の中でさらに計算したら、もうコードを書くだけになった。ただ、数学的に少しわからないところがある。帰ったら4つとも終わっていて、それをコピペしてExcelで足したら、正解だった。結局30時間くらいかかったらしい。そのあと、まともなコードを書いた。普通に書いたらすぐに書けてPyPyで101秒だった。ごり押しした意味が無かった。せこい高速化をしたら32秒になった。まだ速くなりそうだが、もういいことにする。