Project Euler 483

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

49着。3時間。
最初、これならできると思った方向を1週間以上考えていた。しかし、どうしてもうまくいかない。時間がかかりすぎる以前にメモリを消費しすぎる。木曜の帰りに、そういえば最初に今まで考えていた方向より前に思いついてこれはヤバそうだと思ってすぐに捨てた方向があったことを思い出した。電車の中でざっと考えて、帰って書いてみた。あまり状況は変わっていない。しかし、その夜寝ながら考えたら、少し変えればいつもの方法が使えることに気が付いた。金曜日にそれを書いてみたが、やっぱりメモリが足りない。土曜の買い物の帰りに考えていたら、ふとうまく行きそうな分配の方法を思いついた。帰って書いてみたら、速度は10倍以上速くなったが、やっぱりメモリが足りない。そこも小規模の改善をしてなんとかなるようにした。2時間程度で答えが出るようにした。そうすると、今度は答えが合わない。そんなはずはないのだが。どうやら誤差死しているようだ。誤差を極力小さくする方法を使ってみたら、今度はまたメモリを大量に食う。しかも時間も倍くらいかかる。今日になって、Problem 486を考えつつ、より小さい引数で誤差を見てみたら、確かに以前の方法では誤差が大きくなっていた。そこで、何度も失敗しつつ、誤差とメモリが適度に小さくなるように組んでみたら、やっと答えが合った。