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

Project Euler 122(2)

Problem 122200で1.9s、400で20sでした。

Project Euler 121(2)

Problem 1212000で5秒くらいでした。

Project Euler 121(1)

Problem 121この問題は解くだけなら簡単です。

Project Euler 377

http://projecteuler.net/index.php?section=problems&id=377簡単そうに見えるのになぜか答えが合わない。1秒弱、23着。もう疲れた。TwitterにProject EulerのBotがある。これを見ているとめちゃめちゃあせる。 https://twitter.com/projecteulerbot

Blum-Blum-Shub

Problem 375で使われている擬似乱数は sn+1 = sn2 mod d ここで法dはd = pqでpとqは4n+3型の素数です。これをBlum-Blum-Shubというそうです。 知りたいのはこの数列が戻ってくるかです。まず、初項に戻ってこないかもしれないのは当然です。自乗の剰余になれ…

Project Euler 376(2)

http://projecteuler.net/index.php?section=problems&id=376できた。30着。でも20分以上かかった。

Project Euler 376

http://projecteuler.net/index.php?section=problems&id=376問題を理解するのに6分。 ジョギングしてくる。

Project Euler 375

http://projecteuler.net/index.php?section=problems&id=375最初に問題を見たのが10分以上経ってからで、起きだしてから再度見たのがそのあと1時間後。 とりあえず、周期だけわかった。マラソンの応援に行って、そのあと問題に取り組んだ。136s、45着。なぜ…

ラマヌジャンの高度合成数

英語ではHighly composite numberです。これより小さい数は全て、約数の個数が自分のそれより小さい自然数です。なぜこれが重要なのかは知りません。これはProblem 110のコードを少し改変するだけで得られます。1分以内に約数の個数が1012以内の高度合成数な…

Project Euler 107(3) ブルーフカ法

Problem 107今度はブルーフカ法です。日本語での解説ページが見当たらなかったので少し丁寧に説明します。まず、クラスカル法と同様にノード一つの木を全てのノードについて作ります。次に全ての木について、他の木と繋がる辺の中で最も重みの小さい辺を選び…

Project Euler 107(2) クラスカル法

Problem 107次はクラスカル法です。まず、一つのノードのみの木を全てのノードについて作ります。すなわち例では木が7つ作成されることになります。ノードはルート(根)がすぐにわかるようにしておきます。ノードに親を持たせれば、親を辿っていくとルート…

Project Euler 107(1) プリム法

Problem 107この問題は「最小全域木」を求める問題です。最小というのは重みの和が最小ということで、全域というのは元のグラフの全てのノードを持つグラフということで、木というのはループが無い連結グラフということです。この用語さえ知っていればあとは…

Project Euler 374

http://projecteuler.net/index.php?section=problems&id=374ジョギングに出かけてついでに食事するその間に考えて、だいたいの解法が分かったのだが、そのあとなかなか答えが合わなくて。 59秒、63着。 この解法は、O(N1/2)。問題を見ればだいたいわかる。