混乱しそうになったので、調べてまとめてみる。 def f(x, y): print (x, y), return x + yという関数を定義して、 print reduce(f, range(3))とすると、 (0, 1) (1, 2) 3つまり、f(f(0, 1), 2)を計算している。 print reduce(f, range(3), 0)とすると、 (0, …

プロジェクトオイラー http://projecteuler.net/index.php?section=problems&id=273なかなか解けないもんだから日付をまたいでしまった。 数学的な部分は、最初考えていて、分からないからお風呂に入りながらゆっくり考えようと思ったら、湯船に入った瞬間に…

プロジェクトオイラー http://projecteuler.net/index.php?section=problems&id=272 C(n)の求め方を勘違いしていて、間違いに気がついたのが昨日の夜で、これで簡単になるじゃんと思ってコードを書いたんだが、最初個数だと思ってしまって、書き直して和にし…

プロジェクトオイラー http://projecteuler.net/index.php?section=problems&id=271 出遅れたし、272のほうが簡単そうに見えたので最初そちらを考えたら数時間かかるコードになってしまった。271はよく考えたらなんでもない問題だった。

プロジェクトオイラー http://projecteuler.net/index.php?section=problems&id=270 今日は久しぶりに出題の時間に家にいた。 適当に組んでいたら、そのうちにこれは重複が生じないように再帰にする問題だと気がついた。昼食のおかずを買いに出かけていると…

プロジェクトオイラー http://projecteuler.net/index.php?section=problems&id=269 見かけがいかにも数学的なので最初はそういう方向で考えていたが、そのうちこれはコーディングの問題だと気がついた。突飛な発想はまったく要らず、地道に考えながらコーデ…

プロジェクトオイラー http://projecteuler.net/index.php?section=problems&id=268Problem 1と似たような問題の拡張。でも4以上だから包除原理を拡張しないといけないんだが、それに手間取った。これって常識なの？ 範囲が小さいときに有効なコード。 def m…

問題読み違えてた。なんかしらんけど、fは場面で最適なものを選べるのかと思ってた。それでなんとか答えを出してみたものの、答えが合わないので問題を読み直してみたら。 これって、ただの高校数学じゃん。

プロジェクトオイラー http://projecteuler.net/index.php?section=problems&id=267ダメだ、計算量が膨大すぎる。

プロジェクトオイラー http://projecteuler.net/index.php?section=problems&id=266Pythonだととにかくメモリを食う。400MB近く。大きな掛け算を避けるためlogを取るので、それを戻すためにどの素数を使ったのか整数で保持しておく必要がある。その実数と整…

プロジェクトオイラー http://projecteuler.net/index.php?section=problems&id=266風呂入ってまったりしているときに、やっと思いついた。 これ、思いつけるかどうかだけだ。 Pythonだと、メモリ的には限界に近い。

最初Pythonで10分以上かかっていたので、高速化を考えてみた。 列挙する候補の数には、以下の条件がある。 1. 000001で始まる。 2. 1で終わる。 3. 0と1は同数、すなわち16個ずつある。1と2でこうなる。 N = 5 M = 2 ** N L = 2 ** (M - N) def gen_number()…

湯船につかって考えていたらすぐに思いついた。これこそ「逆から考える」だ。すなわち、数が題意を満たすかを調べるのではなく、題意を満たす数を作る。 題意を満たす数は、頭5桁は00000で、一つずらして00001となる。その次は、00010または00011となる。そ…

プロジェクトオイラー http://projecteuler.net/index.php?section=problems&id=265完全に出遅れて、問題文を見たときには40人以上の正答者が。しかも、なかなか問題の意味がわからなかった。 とりあえず、しらみつぶしで答えだけだしておいた。 60番目くら…

色々計算してみたが、何も出てこなかった。 結局、C++で強引にメモリにだけ注意して計算した。 たぶん19番目。もう3日経とうとしているのに。 （追記） 垂心の性質ね。計算してみたら確かにそうなる。そういえばそんなのがあったような気がする。こういうの…

プロジェクトオイラー http://projecteuler.net/index.php?section=problems&id=264どうも、的外れの計算を延々としてしまっていたようで。図形で考えるべきだった。 時間切れなので、明日の午後に考えよう。果たして体力が残っているか。

素数の処理で恐ろしい間違いを犯していたのだが、速度にはそれほど影響がなかった。遅いのは素数の生成の部分だったが、本質的に速くなりそうになかった。Pythonでリストを使うと非常に遅くなることはなんとなく分かっていたので、C++でvectorを使ってほとん…

プロジェクトオイラー http://projecteuler.net/index.php?section=problems&id=263 う〜ん、なんとか答えが出た。 素数はどうしても列挙しなければならないので、部分的なエラトステネスのふるいを使って、triple-pairが見つかったら、その都度practicalか…

プロジェクトオイラー http://projecteuler.net/index.php?section=problems&id=262 そんなに難しい問題ではないと思うけど。 まず、Excelで3-Dグラフを描こうとしたが、どうやって描けばいいか忘れていた。ヘルプを見ても分からないので検索した。 それを見…

あまり速くならない。なぜこのコードでこんなに時間がかかるのか。未だにPythonはどこがネックになるのかわからない。 この問題は、 xy2 = (x + 1)z2 + x(x + 1) という形に帰着する。 s = y / (x + 1) t = z / x とおくと、 (x + 1)s2 = xt2 + 1 xを固定す…

プロジェクトオイラー http://projecteuler.net/index.php?section=problems&id=261 大変だった。ノートを6ページも使った。 いろいろ式をいじくりまわして、ペル方程式に似た式に辿りついた。しかし、これをどう解いていいか最初分からなかった。結局、ペル…

プロジェクトオイラー http://projecteuler.net/index.php?section=problems&id=260 最初、石をどう取ってもloseにならないものをloseと考えたが、逆にloseに石を追加したものをwinとすればよいとわかった。 メモリが足りないのでちょっと工夫した。ただし遅…

プロジェクトオイラー http://projecteuler.net/index.php?section=problems&id=74 この問題もちゃんと考えると面白い。 これも以前解いたときは、題意をそのままコードにしただけだった。 from math import factorialdef next(n): s = 0 while n: m = n % 1…

プロジェクトオイラー http://projecteuler.net/index.php?section=problems&id=73 前にこの問題を解いた頃は、解ければいいや、ということでずいぶん雑にコードを書いていた。この日は9問解いたようだ。 とにかく何の工夫もなくしらみつぶしに調べていた。 …

プロジェクトオイラー http://projecteuler.net/index.php?section=problems&id=257 解けないなあと思って久しぶりに問題文を見たら、条件を見落としていることに気がついた。 a ≤ b ≤ c これだと、 (s-b)(s-c) = nbc s = a + b + c で、nは4以下。4なら正三…

プロジェクトオイラー http://projecteuler.net/index.php?section=problems&id=259 今度は小町算か。 （正確には100になるのを小町算というらしいが、気にしない） この問題は一瞬で解法を思いついた。再帰で解けばいいだけ。たぶん、過去100問で一番易しい…

プロジェクトオイラー http://projecteuler.net/index.php?section=problems&id=258 この問題では、結局2000項の多項式の掛け算に時間がかかる。単純に計算すると、N=2000として、N2回の掛け算が必要となる。実際には自乗の計算なので半分くらいで済む。しか…

プロジェクトオイラー http://projecteuler.net/index.php?section=problems&id=258 大きな項数の問題なので、最初は周期を求めるのかと思った。ふつうに考えれば周期は非常に長いので、特殊な状態なのかと思った。 しかし、多項式であると考えれば簡単。直…

プロジェクトオイラー http://projecteuler.net/index.php?section=problems&id=257 図形の問題かと思いきや、ちょっと計算すると、単なる整数の問題であることがわかる。 from itertools import imapdef gen_triangle(s_limit): for b in range(1, s_limit …

プロジェクトオイラー http://projecteuler.net/index.php?section=problems&id=96 最後に残しておいた問題、それがこのナンプレとか数独とか呼ばれるパズルを50問解く問題。元々これを解くPythonのプログラムは作ってあったのだが、そのためにかえってどう…