n本の棒があります。棒iの長さはa_iです。あなたは、それらの棒から3本を選んでできるだけ周長の長い三角形を作ろうと考えています。最大の周長を求めなさい。ただし、三角形が作れない際には0を答えとしなさい。 プログラミングコンテストチャレンジブック …

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

マージ法（Merge algorithm）は、ソートされた二つの列を合体して一つのソートされた列を作るアルゴリズムです。 原理は非常に簡単です。例えば次のような列があったとして、 2 4 6 8 ... 3 6 9 12 ... まず、両方の列の先頭を比較します。小さいほうの2を取…

http://projecteuler.net/index.php?section=problems&id=305 またなにやら大変そうな問題が。 f(5)すら正しく出ない。 1個間違えていただけだった。でも、f(12)が間違っている。 これもちょっと間違っていただけだった。 f(7780)がすぐに出ないようだと話に…

プログラミングコンテストチャレンジブックにダイクストラ法（Dijkstra's algorithm）の説明が載っていた。Wikipediaに書いてあった説明は意味が分からなかったが、これはわかりやすい。 これは、Project Euler Problem 83を解くときに思いついた方法そのも…

http://projecteuler.net/index.php?section=problems&id=304 解ける気がしない。せっかく久しぶりにスタンバイできたのに。超強引に書いたら解けた。4分半。あとで短くなるように工夫しよう。フォーラムでは5番乗りだったが、解答は4番。4秒差か。工夫して…

フィボナッチ数列Fnは次のように定義されます。 F1 = 1 F2 = 1 Fn+2 = Fn+1 + Fn F2 = 2とする流儀もあるようです。 フィボナッチ数列はいろいろなところに出てくるためか、Project Eulerでもしばしば取り上げられます。フィボナッチ数列をPythonで生成する…

母関数は数え上げや確率の問題で使います。Project Eulerではときどき使えるのでおぼえましょう。最近ではProblem 286で使いました。例えばこんな問題で使えます。 N個のブロックが横一列に並んでいます。赤・青・緑・黄の4色のペンキがあり、これらで各ブロ…

http://projecteuler.net/index.php?section=problems&id=303 この問題はもう200人以上解けているからいいだろう。 nが9の連続（あるいはその倍数）になっているときにf(n)が大きくなることは実験してみるとすぐにわかる。そこで、例えば99で割れる数を出す…

http://projecteuler.net/index.php?section=problems&id=303 やっと問題見た。 100までは割と簡単に出たけど、10000は厳しそう。 うーん、できそうだけど、メモリが足りない。 メモリ使わないように工夫して、できたと思ったんだけど、はねられた。 おかし…

http://projecteuler.net/index.php?section=problems&id=302 コード書いている時間がないので、昨日のコードのままで2時間弱走らせて答えを得た。ただ、3時間以上かかると思っていたので今日に回したが、これなら昨日中に答え出てたなあ。

http://projecteuler.net/index.php?section=problems&id=302 素直に書いてやっと104が出たと思ったら、108が間違っている。 コメントにサイトが落ちているとあったので、リロードしてみたら、確かにアクセスできなくなっていた。でかけている間に、問題文を…

http://projecteuler.net/index.php?section=problems&id=301 6時前に目が覚めて問題文を見る。長い。読もうとするが、眠くてなかなか進まない。問題文を読み終えて、特になにも思いつかないので、もっとも原始的にコーディングしてみる。 def X(stones): if…

nk / nCk < k! + 1 となるnを、明示的になるべく小さくなるように求めようという話でした。このnをNとします。 逆数を取って、 P ≡ 1...(1 - (k - 1) / N) > 1 / (1 + 1 / k!) さて、こういうのはlogを取って積分で近似するのが定番です。 log 1 + ... + log…

http://projecteuler.net/index.php?section=problems&id=300 やれやれ。結局、C++で組んで無理矢理答えを出した。

ネタ元 http://www.kmonos.net/wlog/113.html#_2256100904階乗を求めるのに、 k! = limn → ∞ nk / nCk という方法がある。これはどこかで見たことがあるような気がする。ただ、n = (k + 1)k + 2とすれば必ず整数の割り算で正しい答えは出る、というのは見た…

http://projecteuler.net/index.php?section=problems&id=300 もうすぐ問題が出る。2ヶ月ぶりなので、たぶん問題を理解するだけでも時間がかかるだろう。今日は時間がないので、すぐにわからなかったら風呂に逃げる予定。 なかなか繋がらない。タイトルだけ…

http://projecteuler.net/index.php?section=problems&id=150 Pythonってこういう書き方ができたんですね。知らなかった。 for (i, j), s in izip(gen_index(N), gen_pseudo_random()): これとの連想で、ラムダでもこういう書き方ができます。 lambda (i, j)…

http://projecteuler.net/index.php?section=problems&id=149 よく考えたら、これって左から順に考えたほうが簡単ですね。そうすると、全体の和、最大の和、右端を含む最大の和の3つを考えれば済みます。こうするとコードがすっきりした上、46秒でした。再帰…

http://projecteuler.net/index.php?section=problems&id=149 整数の列に対して部分列の和の最大を求める問題です。 列の長さをnとすると、部分列の決め方でO(n2)、和を取ってO(n3)の計算量になります。和は重複を避けるとO(n2)となります。しかし、これでも…

http://projecteuler.net/index.php?section=problems&id=148 数学的にはよくわかりませんが、実際に数えてみるとわかります。1行で7で割れない数えてみると、明らかな法則性が見えてきます。7進数で考えるとわかりやすいでしょう。その和は、7のべき乗まで…

http://projecteuler.net/index.php?section=problems&id=147 水平の長方形の個数の計算は電卓レベルなので、斜めの長方形について考えます。 この問題はよく考えると、同じ長方形がいくつあるかという数え方と、点を固定してそれを頂点とする長方形はいくつ…

http://projecteuler.net/index.php?section=problems&id=146 すぐにn2は30で割って余りが10でなければならないとわかるでしょう。すなわち、nは30で割って余りが10か20です。しかし、このnに対してまともに素数判定をやっていてはいくら時間があっても足り…

http://projecteuler.net/index.php?section=problems&id=145 題意どおりに書くと、数時間かかりそうです。 def digits(n): while n: yield n % 10 n /= 10 def reverse(n): return reduce(lambda x, y: x * 10 + y, digits(n)) def is_reversible(n): retur…

http://projecteuler.net/index.php?section=problems&id=144 反射ベクトルvは、入射ベクトルv0、鏡の法線ベクトルをnとすると、 v = v0 + k n (v + v0)・n = 0 が成り立ちます。

http://projecteuler.net/index.php?section=problems&id=143 ∠BTC = ∠CTA = ∠ATB = 120°より、 a2 = q2 + qr + r2 b2 = p2 + pq + q2 c2 = r2 + rp + p2 が成り立ちます。個々の整数解はピタゴラス数と同じように求められます。 x = q / a y = r / a と置き…

http://projecteuler.net/index.php?section=problems&id=142 (x - y) + (y - z) = x - z で、3つとも平方数なのでピタゴラス数であることがわかります。あとはzを決めればx, yが決まりますが、単にzの必要な範囲について調べると、20分くらいかかりました。…

http://projecteuler.net/index.php?section=problems&id=141 rがdとqの間のとき、公差をaとして、 n = r + r/a * ra = r + r2 これは平方数になり得ないので、rが一番小さいということになります。そうすると、 n = r + ra * ra2 = r + r2a3 aをs/t（sとtは…

http://projecteuler.net/index.php?section=problems&id=140 Problem 137と同じように見えますが、より難しくなっています。 同じように計算していくと、 (n + 3)x2 + (n + 1)x - n = 0 xが有理数になる必要十分条件は判別式が平方数になることだから、 5n2…

http://projecteuler.net/index.php?section=problems&id=139 単にピタゴラス数で条件に合う組合せを数えても1分くらいでした。 from itertools import * from fractions import gcd def gen_primitive_Pythagorean(L): for m in takewhile(lambda m: m * (2…