2013-03-01から1ヶ月間の記事一覧

Project Euler 36

Problem 36この問題は、単に2と10の両方の基数で回文数になるかを調べるという単純な方法でも十分速いです。自然数nの回文数の判定はO(logn)の計算量なので、NまででO(NlogN)の計算量です。回文数を生成するほうが速いです。10進で回文数を生成して、2進で回…

Project Euler 420

http://projecteuler.net/index.php?section=problems&id=42050着。PyPyで1秒、Pythonで9秒。 デバッグをずっとしていたが、平日だとなかなか集中してできないので厳しい。 もうちょっと速くなるはず。

PriorityQueueの使い方

Project Eulerでしばしば、○○を満たすN未満の最大の整数を求めよ、といった問題を見かけます。例えば、Problem 26です。この問題を読み替えると、「10がFpの生成元になるN未満の最大の素数を求めよ」とほぼなります。こういう問題は、N-1から順番に整数が題…

Project Euler 419

http://projecteuler.net/index.php?section=problems&id=41977着。PyPyで6秒。 昨日の帰りに思いついた。思いつかないとなんともならない。 もうちょっと削れそうなんだけど。

今日のバグ

今日ほとんど使わない機能のテストをしていてずっとバグに悩まされていました。結局、こんな感じのバグでした。 for(int i = 0; i < 5; ++i) b[d] = a[i]; わかりますか?添え字が間違ってますよね。こんなのが10年くらい放置されていたみたいです。こういう…

PyPyを速くする(1) sort

PyPyは同じソースを動かしてもPythonよりたいてい速いのですが、遅くなることもあります。その対処法がいくつかあるので紹介していきます。今回はリストのソートです。こんなコードを動かしてみます。 from itertools import * import time def gen_S(): S =…

Project Euler 418(3)

http://projecteuler.net/index.php?section=problems&id=418どうやら、多倍長整数(long)がリストに混じっているとPyPyのソートが遅くなるらしい。そこを改善して、あとこちょこちょと直したら、Pythonで0.09s、PyPyで0.1sになった。まだPyPyのほうが遅い…

Project Euler 418(2)

http://projecteuler.net/index.php?section=problems&id=418真面目に組んだら1.4sになった。そこからせこい高速化をしたら0.2sになった。 PythonよりPyPyのほうが2倍くらいかかっている。なぜなのか明日調べたい。

Project Euler 418

http://projecteuler.net/index.php?section=problems&id=41845着。なんかよくわからんが適当に組んだら正解が出た、としか言いようがない。

Project Euler 417(2)

http://projecteuler.net/index.php?section=problems&id=417ちょっと工夫したら2分半になった。80倍くらい速くなった。

Project Euler 417(1)

http://projecteuler.net/index.php?section=problems&id=41777着。 朝起きて問題だけ見て出かけた。車内で、こんなの簡単だろうと思ったので、コピペせずに一から組んでみた。しかし、遅い。とてもネットブックでは答えは出せない。夜家に帰ってきて回して…

Project Euler 355

未解決問題を解こうシリーズ第9弾。http://projecteuler.net/index.php?section=problems&id=355307着。15秒。 ずっとわからなかった。先週ジョギング中に考えたらちょっと思いつくところがあって、それを昨日の帰りに考えていたらわかった。これで多少は絞…