例えば、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)となります。 ガウス整数の約数を計算しなけ…

http://projecteuler.net/index.php?section=problems&id=312 38も32とだいたい同じだった。結局、オイラーの定理を使うだけだった。けど、これは結果知ってないと出てこない。しかも、これは3と13の絶妙な関係で成り立つものだし。 コードも改良して1msくら…

http://projecteuler.net/index.php?section=problems&id=312やっとC(10000)が出た。1時間もかかった。で、そのあとどうやってやるの？ えー、できたと思ったのに×。 あー、わかった。つまらないトラップにひっかかってた。 できた。64秒、11着。 理屈はまっ…

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

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

http://projecteuler.net/index.php?section=problems&id=311 かろうじて24時間以内に20位以内が埋まったらしい。 16着だったが、14着と1分38秒差、13着とは3時間半以上の差。これはミラクルとしか。30分くらい席を外して放置していて、見てみたらできていた…

http://projecteuler.net/index.php?section=problems&id=311 なかなか繋がらないなあ。 やっと繋がった。今日はHardのはずだから、目標は正午まで。 なにも思いつかない。 やっと49出た。なんか知らんがもっと少ないと記憶違いしていて、なぜこんなに多く出…

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

昨日アップする順番間違えた。前回の結果、プロセスは2つの子プロセスを発生させるとき、 N E 1 1.0 2 1.5 3 2.0 4 2.33333333333 5 2.66666666667 6 3.0 7 3.33333333333 8 3.58333333333 9 3.83333333333 10 4.08333333333となりました。さらに、 0 ／ 1 …

ガウス整数は、a, bを整数としたとき、a + ibと表せる数を言います。 ガウス整数は、素因数分解の一意性があります。例えば5なら、 5 = (2 + i)(2 - i) と一意に分解できます。ただし、-1、±iを掛けた数は同じ因数とみなします。すなわち、 5 = (-1 + 2i)(-1…

http://projecteuler.net/index.php?section=problems&id=310 起きたとき、すでに26人正答。 Grundy数を求めるだけなら簡単だけど、普通にしらみつぶししていては間に合わない。 できた。31秒。最後、重複を排除するのがややこしかった。正答者31人。

期待値は再帰的に計算することができます。例えば、N=4、M=2なら、 0 ／ ＼ 1 2 ／ 3となりますが、各プロセスを殺すと、0を殺すと全て殺せて、残りは、 1: 0 2: 0 3: 0 ＼ ／ ／ ＼ 2 1 1 2 ／ 3となります。これらのプロセスツリーに対する期待値を計算し…

http://b.hatena.ne.jp/entry/d.hatena.ne.jp/halhorn/20100904/1283612722 これを真似しようとしていて。Project EulerのProblem 309で素直に解くとソートが遅いので、並列処理で速くならないか、じゃあ配列を4等分して、それぞれ並列でソートして、それを…

http://projecteuler.net/index.php?section=problems&id=308 ちょっと工夫したら8秒になった。

http://projecteuler.net/index.php?section=problems&id=309 ごく素直に書いたら3分弱で答えが出てきた。しかし、はねられた。何がまずいんだろう。これ以上ないほど素直に書いたので確かめるのが難しい。 ああ、100万以下じゃなくて100万未満か。 明日以降…

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

http://projecteuler.net/index.php?section=problems&id=308 検索をするとヒントになるようなページが出てくる。これを読むと、なるほどだから素数になるんだとわかる。ちゃんとわかったわけではないが。とにかくこれがヒントになって、あとは速くなるよう…

以前やったように封筒から取り出した回数で分類して速くならないでしょうか。 例えば、A3を使うとして状態が(0, 0, 1)だったとすると、取り出した回数が3回なので、A4までで考えると、(0, 0, 1, 3), (0, 0, 1, 2), (0, 0, 1, 1), (0, 0, 1, 0)の状態が考えら…

元のコードはこうでしたが、 from itertools import izip, count def next(s, k): return s[:k] + (s[k] - 1,) + tuple(n + 1 for n in s[k+1:]) def E(s): num_papers = sum(s) if num_papers == 0: return 0.0 return (1 if num_papers == 1 else 0) \ + s…

あれこれ考えたのですが。 例えば、必要な紙がA3だったとしましょう。すなわち、A4、A5まで紙は切られません。そうすると取りうる状態は、 (1, 0, 0), (0, 1, 1), (0, 1, 0), (0, 0, 2), (0, 0, 1), (0, 0, 0)の6つになります。同じ手順でA4が必要だったとし…