http://projecteuler.net/index.php?section=problems&id=373S(100)出た。しかし、絶望的に何も思いつかない。 やっとS(1200)出た、と思ったら微妙に値が違うなあ。またかぶっているのか。しかも10万でも40秒。

Problem 100ラストです。 合計のディスクの枚数をn、青いディスクの枚数をbとすると、 (b/n)( (b-1)/(n-1)) = 1/2 です。変形していくと次のようになります。 (2n - 1)2 - 2(2b - 1)2 = -1 これはPell方程式ですね。 x2 - 2y2 = -1 の解は、 x + y√2 = (1 + …

http://projecteuler.net/index.php?section=problems&id=372朝ちょこちょこっと直したら正解でた。46秒。49着。 第1感はちょっと間違っていた。それで大回り。いや、方向は間違っていなかったんだが。 これ、速くならないのかな。 フォーラムが異常に閑散と…

http://projecteuler.net/index.php?section=problems&id=372微妙に合わないなあ。時間的には問題ないんだが。

http://projecteuler.net/index.php?section=problems&id=372第1感でいけそうな感じなので、これから少しずつ組んでいく。まずは基本のところから。

Problem 99logを取るだけで十分です。

http://projecteuler.net/index.php?section=problems&id=37210時にこの問題を見てそれから風呂に入って考えようと思ったが、どうもこの問題は手を動かさないとダメのようだ。ただ、少し思いつくところがあったのでそちら方向で考えてみようと思う。だいたい…

Problem 98アナグラムは次のように探します。例えば、CAREをアルファベット順に並べるとACERになります。RACEも同じです。こうして同じになったものがアナグラムです。まずそうやって全ての単語を調べます。groupByを使うと簡単ですね。ScalaのgroupByはソー…

Problem 97これはシェルピンスキー数というものを調べているときに発見された巨大素数らしいです。 多倍長整数を使えば、 println (((BigInt(1) << 7830457) * 28433 + 1) % 1e10.toLong) これだけです。 しかし、いくらなんでもこれでは芸が無いので、64ビ…

Problem 96数独は深さ優先探索で簡単に解けます。左上から空欄に順番に数字を埋めて、縦横正方形で重複が無ければ隣に移ります。ダメなら次の数字、それでもダメなら元に戻ります。

http://projecteuler.net/index.php?section=problems&id=371今朝コードを見直してみたらかつてないほどひどいミスをしていることに気が付いた。

http://projecteuler.net/index.php?section=problems&id=371今朝考え直して、自信満々でサブミットしたらincorrect. やっぱり読み間違えているようだ。

http://projecteuler.net/index.php?section=problems&id=371英語がよくわからないけど、これってためていくってこと？ できたと思ったがincorrect. すでに17人正答。

http://projecteuler.net/index.php?section=problems&id=34これもProblem 30とほとんど同じです。 重複組合せを使う方法に対して、8倍くらい速かったです。

http://projecteuler.net/index.php?section=problems&id=30以前のと違う方法をふと思いついたので書きます。例えば、6桁として456789を考えます。 45 + 55 + 65 + 75 + 85 + 95 - 456789 が0ならいいわけです。ここで3桁ずつにわけて考えましょう。456000と…

Problem 94等辺以外の辺の長さは偶数です。奇数だとすると三角形を対称軸で半分に割った三角形の各辺を2倍した直角三角形の斜辺は偶数で、別の辺は奇数です。そうするともう一つの辺の平方は4の剰余が3となって矛盾です。そこで先ほどの辺を2bとして等辺をa…

Problem 93四則演算の関数を定義しておくとリストにできて書きやすくなります。

http://projecteuler.net/index.php?section=problems&id=370昨日電車の中でノートに書いて帰ってコード組んでみたが全然合わない。今日なんとかバグを取って、41着。しかし、1時間以上かかった。どうやったら速くなるのかわからない。あとから考えるからフ…

朝からのどが少し痛くて体がだるいが、走っていれば治るかもしれないと思って参加する。 走っていても調子が上がってこない。体調の悪さの表れだろうか。5kmでもう疲れている。スタジアムの裏手の坂を上っていると抜かれそうになる。水色のユニに黄色いゼッ…

Problem 92よく考えたら、これは長い多項式の掛け算だからKaratsuba法が使えますね。Scalaは多倍長整数の掛け算が遅いので特に効果が大きいはずです。 これくらい速くなりました。 1050 0.6s -> 0.12s 10100 3.4s -> 0.5s 10200 28s -> 2.4s

http://projecteuler.net/index.php?section=problems&id=370今日はあまり時間がない。それでもちょっと空いた時間に考えていたらできそうだ。でも組んでみたら答えが全然違う。頭の中ではできているつもりなのに。

Problem 92母関数を使うと圧倒的に速くなります。 1桁の場合母関数を次のように表します。 P1(x) = 1 + x + x4 + x9 + ... + x81 これは、各桁の平方和が0, 1, 4, 9, ..., 81になる場合が一つずつあり他は0ということを意味しています。2桁の場合は、 P2(x) …

Problem 92数字が入れ替わっても次は同じです。例えば23 -> 22 + 32 = 13、32 -> 32 + 22 = 13です。こういうときは重複組合せですね。なのですが、場合の数を計算しやすいように、 1 1 1 2 2 3 4とするところを、 (1, 3) (2, 2) (3, 1) (4, 1)としました。 …

Problem 92107までなので、チェーンの次は92*7以下になります。だからそれ以下をあらかじめ1か89のどちらに帰着するかを調べておきます。

Problem 91前回の3を効率よくします。Pを固定してQをPが直角になるように配置します。例えば、L = 10として、P(4, 6)としましょう。OPと直交するベクトルは(6, -4) = 2(3, -2)だから、Qは(4 + 3t, 6 - 2t)と書けます。Qのx座標は10以下だからt L = 10000で10…