http://projecteuler.net/index.php?section=problems&id=514
32着。2分半。
方針はちょっとややこしいが割と簡単に立った。それに沿って月曜にコードを書いた。しかし、E(2)すら合わない。E(1)は合った。
デバッグをするのだが、なかなか手計算と答え合わせをするのも難しい。それで2×1で手書きしてみた。そこでいくつかバグを見つけたと思ったが、そのたびにあとからバグでないことに気づいた。
結局、昨日の夕方からナイーブに書いてみた。凸包を求めるコードは昔仕事で書いたことがあった。それでもめんどくさいと思っていたのでやらなかったが、しょうがない。なんとか書いてE(2)を計算してみると合わない。もう一度問題を読んでみたら、大事な部分を読み落としていた。そこを修正したら、ナイーブなコードでE(2)が合った。結局ここが間違っていたのだ。それに合わせて本番のコードも修正したら、見事に合った。E(10)も合った。あとはスピードの問題だけで、20、30、40、50、60、70と計算して、100は5分くらいかと思って計算させてみたら2分半だった。
たぶんO(N^5)だと思う。定数倍速くする方法はすぐに思いつくのだが、それより速くする方法がわからない。でも、これを書いていて思いついた。これがうまくいったら、フォーラムに書いてみよう。フォーラムの方法はよくわからなかった。
さっき思いついたところは直して、34秒になった。速くしていない部分が30秒以上を占めているので、そこを速くしようとしているが、なかなかうまくいかない。今日はギブアップだと思う。
