関数 前回、Problem 1を解きましたが、その際3と5と15で同じ処理を繰り返していましたね。こういうときに関数を使いたくなるのがプログラマです。 まず簡単な、整数を引数にして5倍する関数を例にしましょう。 @echo off call :five_times 3 echo %ERRORLEVE…

最近、バッチファイルでコーディングする機会があって、バッチファイルでもがんばれば意外とできるのではと思ったので、Project Eulerを解いてみることにしました。 バッチファイルについては、最初はバッチメモを参考にしました。あとは、コマンドラインでs…

最初に戻って、素数のガウス整数の素因数を格納するときに、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)となります。 ガウス整数の約数を計算しなけ…

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が必要だったとし…

この問題は前回やったようにメモ化を使って簡単に解けますが、動的計画法（DP）ではどうでしょうか。DPの問題点はどの状態になるかどうかわからないところです。よく例に出されるフィボナッチ数列なら、n項をFnとして、F1 = F2 = 1として、F3から順に求めて…

http://projecteuler.net/index.php?section=problems&id=308 少し出遅れた。 英語が全然わからないんだけど。 10分経ったらわかってきた。 2のべきなんか出てこないと思ったら、打ち間違えていただけだった。 2の83乗まで出てきたが。 解ける気がまったくし…

メモ化（memoize）は、Project Eulerで何問かに1問必ず使う手法なので、絶対に覚えましょう。 Project EulerのProblem 151を考えます。意味が分かりにくい問題ですが、分かれば簡単です。まず最初にA1の紙が1枚封筒に入った状態を考えます。この状態を (1, 0…

http://projecteuler.net/index.php?section=problems&id=306 この問題はまともに解くとDPで2つ前の項を使うのでパッと見は並列化できないように思えるが、少し工夫すればほぼ並列化できる。 4分20秒くらいだったのが、4コアで並列化して69秒になった。4分切…

さて、元の問題をもう一度。 n本の棒があります。棒iの長さはaiです。あなたは、それらの棒から3本を選んでできるだけ周長の長い三角形を作ろうと考えています。最大の周長を求めなさい。ただし、三角形が作れない際には0を答えとしなさい。 プログラミング…

http://projecteuler.net/index.php?section=problems&id=307 どうしてもオーバーフローする 間違えていただけだった。ムダに時間を費やした。5着。 これ、すぐに誕生日の問題と同じだと気づいたのに。 まあ、食事の時間の前に片がついたのはよかった。 フォ…