http://projecteuler.net/index.php?section=problems&id=459この問題は唯一解けずに残っている問題である。 とりあえず一次元ならどうかと考えているのだがわからない。前のコードを書いたときはPyPyで21まで答えが出た。今回少し工夫してスピードアップし2…

http://projecteuler.net/index.php?section=problems&id=468いろいろ小手先の高速化を施したら、PyPyで7分が5分になった。 そして、最後に小手先といえば小手先だがフォーラムにも無い方法で高速化したら3分になった。 それをC++に翻訳したら18秒だった。 …

http://projecteuler.net/index.php?section=problems&id=46988着。 O(N)の方法はすぐに思いついた。しかし、これでは何年もかかる。 今朝考えていて近似を使うのかなと思って、ややこしい方法を思いついた。 しかし、こんなことをする必要はなかった。騙さ…

Problem 468の計算量を見積もるときにこんな問題が思い浮かびました。 N以下を素因数分解したとき、素因数の個数の平均は？ 例えば、2、3、4 = 22、5なら1個、6 = 2 * 3なら2個とします。logNよりはずっと小さいと思われます。とりあえずコードを書いて調べ…

http://projecteuler.net/index.php?section=problems&id=46841着。7分。 土曜に風呂に入って考えたら簡単じゃないかと思った。しかし、日曜に組んでみると遅い。なぜ遅いのかわかった。O(N^2/logN)くらいになっているはず。しかし、C++でごり押しができるく…

http://projecteuler.net/index.php?section=problems&id=467103着。40分。 火曜の朝には解法に気づいていたが、コードを書く時間が無かった。 Pythonは多倍長整数が作れるからそのまま使えば速いと思って楽なコードを組んだが、最初はメモリエラー、必要な…

http://projecteuler.net/index.php?section=problems&id=46557着。3分。 月曜日にナイーブな実装をしてから、これはグラフの問題だと思った。しかし色々考えてもなかなか解に近づきそうにない。検索してもそれらしきものが出てこない。一方で、この巨大な空…

http://projecteuler.net/index.php?section=problems&id=46677着、4分。 先週の日曜日には解法を思いついていた。しかし平日はコーディングする時間が無い。昨日やっとコードを書いてあとは高速化するだけだと思っていた。今朝ある程度高速化したが、ある瞬…