http://projecteuler.net/index.php?section=problems&id=472
18着。
最初、問題の図にあるようなナイーブな実装もなかなかできなかった。しかも、これだとN = 500さえ難しい。個数だけなら簡単だと思って組んでみた。しかし、これだとO(N^2)かかる。O(NlogN)を思いついたので、昼を食べたから、頑張って組んでみた。しかし、これでは2e6秒以上かかりそうだ。しかも、PyPyでこれでPythonなら30倍以上かかった。つまりC++で書いても劇的には速くならないということだ。
昼寝しながら考えた。こんなO(NlogN)は要らなかった。全く回り道をした。何度も何度もナイーブな実装と比較してバグを潰しながら組んだ。
