http://projecteuler.net/index.php?section=problems&id=42744着。出題されてから18日もかかった。 どう計算してもO(n^2)すらならなかったが、日曜に少し考えたらO(n^2)になった。しかし、これだと莫大な時間がかかる。少しずつ工夫してC++で3コアで回せば2…

http://projecteuler.net/index.php?section=problems&id=42973着。 問題見て考えたら簡単で、100番台でもこんな簡単な問題ないぞと思って、スクラッチから書き始める。それを実家の超絶遅いPCで流すこと25分。0という答えが出た。そこで時間切れ。もう出な…

http://projecteuler.net/index.php?section=problems&id=42825着。 とにかく数式変形が大変で。Mathematica的なものがあれば楽だったんだろうけど。昔自作したんだけど、途中で挫折したんだっけ？ まだPyPyで40分以上かかっているのでなんとかしたい。帰り…

例えば、こんなコードがあるとします。 def divs1(N): return [ N / n for n in xrange(1, N + 1) ] N = 10 ** 8 print sum(div1(N)) 内包表記ですね。これを間違ってもappendを使って次のように書いてはいけません。 def divs2(N): a = [] for n in xrange(…

// 範囲選択モードなら、選択範囲を次の単語の右に伸ばす // そうでなければ、カーソルにある単語を選択する if(selecting) { wordrightsalnen; } else { #x0 = x; #y0 = y; selectword; #x1 = seltopx; #y1 = seltopy; // message(str(#x1) + "," + str(#y1…

http://projecteuler.net/index.php?section=problems&id=42577着。 簡単な問題なのに、見落としがあって2時間以上かかってしまった。F(10^4)が合っていてもF(10^7)が合わなかった。

http://projecteuler.net/index.php?section=problems&id=42426着。 数独の時と同じようにしらみつぶしに調べればいいだろうと思っていたが、予想以上に時間がかかる。何問かどうしても答えを出すのに時間がかかる問題が出てきた。それは、手で途中まで解い…

例えば素因数分解を与えて約数を全て列挙するコードを書きます。こんな感じでしょうか。 def pows(n, e): yield 1 q = 1 for _ in xrange(e): q *= n yield q def divisors(fs): if not fs: yield 1 else: p, e = fs[0] qs = pows(p, e) for n in divisors(f…

Project Eulerの問題の難易度としては解いた人の数が使われますが、これよりも最初のほうの人が解くまでにかかった時間のほうが実態に合っていると思います。ここでは、Problem304〜422の50人解けるまで時間を調べてみました。特に上のほうは100番台レベルで…

http://projecteuler.net/index.php?section=problems&id=42363着。 きのう簡単なところがどうしてもうまく書けなくて。 そこが書けたら、あとはふつうに高速化するだけだった。 たぶん一番時間がかかっているあそこを工夫すれば速くなると思うんだけどな。

Problem 1を考えます。ふつうに書くとこんな感じです。 N = 10 ** 8 # オリジナルは1000 print sum(n for n in xrange(1, N) if n % 3 == 0 or n % 5 == 0) この問題はプログラマを関数型に導くためのものなのです。 これを動かすと、Pythonで13秒、PyPyで3.…

http://projecteuler.net/index.php?section=problems&id=42238着。かかった時間は測定不能レベル。 地道に計算すればそんなに難しくない。

Problem 277から421までのランクイン数のランキング 4/6 16:00頃現在 ID別 rank ID country frequency 1 x22 Slovakia 144 2 aleksey Ukraine 131 3 uwi Japan 126 4 triceps Japan 109 5 umu Germany 107 6 Tepsi Hungary 102 7 Anton_Lunyov Ukraine 100 8…

http://projecteuler.net/index.php?section=problems&id=421いろいろがんばって87秒になった。これ以上は無理そう。

http://projecteuler.net/index.php?section=problems&id=42159着。PyPyで110秒。 昨日解法わかったが、体調悪くてコードを組む気力がなかった。比較的簡単なのに。 もうちょっと速くなると思うけど、うまくいかない。

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

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

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

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

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

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

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

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

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

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

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

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

http://projecteuler.net/index.php?section=problems&id=416昨日PyPyがあまり速くならなかったが、原因がわかった。 多倍長整数同士の掛け算になっていたところは、整数同士の掛け算にするとPythonではあまり関係ないが、PyPyだと速くなる。たとえその掛け…

http://projecteuler.net/index.php?section=problems&id=41640着。 日曜の夜の時点ではランクインするとは思わなかった。このサイクルも幸先よいスタートを切った。 Pythonで12分、PyPyで7分。 この問題はnumpyが使えそうで使えない。オーバーフローするた…

http://projecteuler.net/index.php?section=problems&id=41525着。 PythonをC++に翻訳したら1CPUで10時間の見込みになったので、4CPUが使えるように4つのバッチファイルにして、合計5000の実行ファイルをキックして、最後に集計。C++のネックは、 std::cout …