エラトステネスのふるいの速度を確認します。まずは最も単純なもの。 def sieve1(N): a = [ True ] * (N + 1) for p in takewhile(lambda p: p * p <= N, (n for n in count(2) if a[n])): for k in xrange(p * 2, N + 1, p): a[k] = False return [ n for n…

昨日ひどかったので考え直してみました。要するに試し割りの回数がわかればいいのです。もちろんわからないので、n前後の試し割りの回数の平均を求めます。ガウスの故事に倣って1000個ずつ取って平均します。なるべく長いスパンで見たいので、平均を取る範囲…

どの素数判定法を使うべきか迷うことがあるのでまとめてみます。 試し割り法 ある整数が素数であるか2から順に割っていきます。nが素数かどうかの判定には√nまでの素数で割り、全て割り切れなかったら素数です。途中で割り切れたらその時点で合成数と分かり…

よく知られた方法に行列の片方を転置して掛け合わせるという方法があります。 通常のように AikBkj としてkで回すと、Bのほうは飛び飛びのアドレスを見ることになり、キャッシュのヒットミスが起こりやすくなります。わざわざ転置してから、 AikBjk とすると…

最初に戻って、素数のガウス整数の素因数を格納するときに、2つ配列を作ってそれぞれに実部と虚部を格納していましたが、よく考えるとそれぞれは10000以下なので、16ビットごとにそれを格納して一つの整数にすればよいですね。 そうすると、それでも250MBく…

5の約数は、1, 2 + i, 2 - i, 5ですが、整数は足して考えてもよいです。ai + bii(ai ≥ bi ≥ 0)に対して1と5を掛けると、ai + bii, 5ai + 5biiとなり、90度回転したbi - aii, 5bi - 5aiiと実部の和を取ると、6ai + 6biとなり、最初から6としたときと同じにな…

例えば、5の実部が正の約数は、 1, 2 + i, 1 - 2i, 2 - i, 1 + 2i, 5 ですが、15の約数は、5の約数とそれを3倍したものになります。すなわち、s(15) = 4s(15)となります。105なら、s(105) = (1 + 3 + 7 + 21)s(5)となります。 ガウス整数の約数を計算しなけ…

素因数分解をするのではなく、素数の積を生成するのと同じ方法で約数の組を作っていきます。最も素直に書いてみました。 しかし、やっぱり遅いですね。

素因数分解ができればガウス整数での約数の和が求められるようにしましょう。 まず、素数のべき乗について考えます。例えば、3はガウス整数でも素数なので9なら約数は(1, 3, 9)です。一般に4の剰余が3なら同じようになります。 5 = (2 + i)(2 - i)なので、5e…

この問題はメモリを多く使えば簡単のようですが、いつもやっているように300MBを目標にしてPythonでなるべく速くなるようにします。ガウス整数の範囲で約数の和を求めるということなので、素因数分解ができれば約数は簡単に求められるでしょう。ガウス整数の…

こうやるんだ、知らなかった。 from functools import partial def f(x, y, z): return (x * 10 + y) * 10 + z g = partial(f, 1, 2) print g(3) # 123

元ネタ 曖昧な数値を曖昧なまま計算できるPythonのモジュール uncertainties これを読んだときはあまりよくわからなかったけど、インストールしていざ使ってみると、これはそんなに簡単なものではないようです。 from uncertainties import ufloat from unce…

プログラミングコンテストチャレンジブック作者: 秋葉拓哉,岩田陽一,北川宜稔出版社/メーカー: 毎日コミュニケーションズ発売日: 2010/09/11メディア: 単行本（ソフトカバー）購入: 52人 クリック: 1,538回この商品を含むブログ (83件) を見る4.2のゲームか…

プログラミングコンテストチャレンジブック作者: 秋葉拓哉,岩田陽一,北川宜稔出版社/メーカー: 毎日コミュニケーションズ発売日: 2010/09/11メディア: 単行本（ソフトカバー）購入: 52人 クリック: 1,538回この商品を含むブログ (83件) を見るまだ4割ほどし…

元ネタ http://python-history-jp.blogspot.com/2010/09/pythonc.html Pythonのこの挙動、知らなかった。 print -1 / 3 # -1 print -1 % 3 # 2 C++なら、 std::cout << -1 / 3 << std::endl; // 0 std::cout << -1 % 3 << std::endl; // -1 何度この挙動に悩…

単に問題文の最後を読み間違えていただけ、というかちゃんと読んでいなかっただけだった。

うーん、できたと思うんだが、どこが間違っているのかわからない。

プロジェクトオイラー http://projecteuler.net/index.php?section=problems&id=283 1時間寝坊。まだ誰も解けていないようだ。今日もあまり時間取れないのに。

ちょっといじったら正解になった。 n = 5以上は数学的にはよくわからんが、マジックで比較的簡単。n = 3以下は手作業で求められる。結局、n = 4のときが問題だが、これもそんなに難しくない。 間違えた。4以上なら同程度だが、5以上の場合マジックが効く。 …

考え方変えたら割と簡単な漸化式が出てきて解けた。 対称性で考える。 なんとかの補題ってので簡単になるらしい。

プロジェクトオイラー http://projecteuler.net/index.php?section=problems&id=281 まず、f(3,2) = 16が手でなかなか出てこなかった。 雑なコードは割とすぐ書けた。 手がかりはあるのだが、あと1時間できる自信がない。

プロジェクトオイラー http://projecteuler.net/index.php?section=problems&id=280 問題の意味を理解するのに5分。正しく理解したのかは不明。 the lower row, the upper rowの解釈に自信がない。 2×2マスの場合はできたと思うんだけど、それ以上はどうして…

プロジェクトオイラー http://projecteuler.net/index.php?section=problems&id=279 こういう問題文が短いものは難しいにちがいない。時間もあまりないしゆっくりやろう。 すぐにいつものパターンであることがわかった。しかし、なかなかうまくいかない。結…

プロジェクトオイラー http://projecteuler.net/index.php?section=problems&id=278 やっとfが計算できるようになった。道のりは遠そう。 fの計算が速くなった。でも、このfで計算したら一生かかりそう。 p = 2のときができた。なんで他はできない？ 元の計…

プロジェクトオイラー http://projecteuler.net/index.php?section=problems&id=277 231は出たのに、なんで1004064は出ないのよ。 どうも不定方程式のプログラムが間違っているらしい。 なんとか答は出た。不定方程式のコードは符号が違うとうまく動かない代…

プロジェクトオイラー http://projecteuler.net/index.php?section=problems&id=276 格闘してるけど、なかなかできない。aが素数のときだけはできたけど。 方針変えたら割と簡単にできた。なんということもなかった。 スコア見ると6位か。 やっと速くなった…

やっと出来た。 最後は14時間かかった。 メモリはせこい方法で節約。2行を1行分に圧縮。それから、Pythonではタプルより多倍長整数のほうがメモリを食わないらしい。最後に、簡単に求められる部分をあらかじめ求めておいて、その解は記憶しないようにして、…

土日から方針を転換してみたら、15次は正しい値が出た。しかし18次はメモリ的にも時間的にも無理そう。17次ならいけそうだけど。メモリを使わないようにするにはユニークな解を生成すればいいのだけれど、どうしてもそれができない。

プロジェクトオイラー http://projecteuler.net/index.php?section=problems&id=275 出題が寝ている最中1時で、4時半になぜか目が覚めて枕もとのネットブックで問題を見てみた。まだ3人しか解けていない。回らない頭でなんとか問題を理解して考えた。バラン…

おいおい、こんなに簡単にできていいのかよ。問題解く時間より、問題読む時間のほうが長かったような気が。 フォーラムで3番だけど、実際の順位は？ 風呂に入ってもっといい方法を考えよう。 世界ランクトップに立つ。なんという幸運。もう二度とこんなこと…