http://projecteuler.net/index.php?section=problems&id=416
40着。
日曜の夜の時点ではランクインするとは思わなかった。このサイクルも幸先よいスタートを切った。
Pythonで12分、PyPyで7分。
この問題はnumpyが使えそうで使えない。オーバーフローするため。オーバーフローを無視すると23秒になる。
8桁ならオーバーフローしないので使える。発想を変えると、8桁だけ求めて頭の数字はしらみつぶしにしてもいい。この手の問題の場合、たいてい頭に0が来ることはないので、1〜9で平均5回入力すれば正しい答えが出る。1回入力すると30秒入力できなくなるので、4回の待ち時間は2分。結局2分半くらいかかることになり、PyPyの7分より速い。
少し工夫するとnumpyが使える。これで44秒になった。明日にでもフォーラムに書こう。
