Problem 91直角三角形を3通りに分けて考えます。 Pがy軸上でQがx軸上のもの Pがy軸上でQはその右、またはQがx軸上でPはその上 P、Qは軸上にないもの 上の2つは簡単です。L = 50として、最初の場合はL^2個、次の場合は2L^2個あります。 3番目は、図のようにP…

http://projecteuler.net/index.php?section=problems&id=368フォーラムでレスをもらったが、コードが理解できない。ループの中で複雑なことをされるとまずわからない。文章でなんとなくわかったけど。

http://projecteuler.net/index.php?section=problems&id=3693.5秒。37着。 きのう考えようと思ったがまったく頭が働かないので早めに寝た。 今朝電車の中で考えたらいろいろとアイディアが浮かんできた。最後に出てきたアイディアは非常に計算がクリアにな…

http://projecteuler.net/index.php?section=problems&id=369久しぶりにスタンバイ。 まずBadugi単語を調べる。 簡単そうに見えるのに、f(5)すらちゃんと出てこない。 やっとf(5)が出た。この方向で考えてみるか。

Problem 90全探索でOKです。

Problem 89ローマ数字をIntに直してさらにローマ数字に変換するだけですね。

Problem 88これも素直に解きます。pを積、sを1以外の和、nを1以外の項数とすると項数lは l = p - s + n となります。これは1以外の項を追加すると常に大きくなるので（1の項は積と和が等しくなるように個数を調整する）、12000以下になるように列挙できます…

Problem 87これは素直に解くしか無さそうです。同じ和でも別として数えるのならやり方もありそうですが。

http://projecteuler.net/index.php?section=problems&id=368フォーラムにあった論文をちょっと見たが、たぶん同じ考え方だった。残念。Mathmaticaってそういう意味だったか。 昨日最初に考えようと思った、数字が3つ続かない数を数えてみましょう。 ak,mを…

http://projecteuler.net/index.php?section=problems&id=368昼前に戻ってきて問題を見たところだが、まったく何も思いつかない。シャワーを浴びながらホントに収束するか考えたがはっきりはわからなかった。そのあとすぐに食事に出かけた。そこで考えていた…

Problem 86(a, b) = (3, 4)のとき、3を分割する場合の数は1で、4を分割する場合の数は2です。相似の三角形を考えると、M = 20として、前者は(15, 20)まで、後者は(18, 24)まであります。それぞれの個数は、 1 + 3 + 4 + 6 + 7 = 21 2 + 3 + 4 + 5 + 6 + 7 = …

Problem 86直方体の3辺の長さをp, q, r(p < q < r)としてp + qとrが直角を成す三角形の斜辺が整数になる場合を求めるのでしたが、逆にピタゴラス数(a, b, c)(a < b < c)が先に与えられた場合を考えます。例えば、(3, 4, 5)というピタゴラス数を考えます。斜…

Problem 87単に1分以内に収めたいだけなら次のようにすればよいです。最大の辺が1, 2, 3, 4, …となる直方体の数を数えていけばよいです。47秒でした。 ただ、この方法は発展性が無いんですよね。

Problem 86直方体の3辺の長さをp, q, r(p < q < r)とすると、距離の自乗は (p + q)2 + r2 なのでこれが平方数ならば最短経路が整数になります。直方体の数を求める最も簡単な方法はp, q, rを列挙することです。これはO(M3)かかります。これでは箸にも棒にも…

http://projecteuler.net/index.php?section=problems&id=36740着。 きのうの昼に思いついた方法を。かなり手を抜いたけど。 フォーラム見たら、みなたぶん同じような方法。思いつけばなんとかなるけど、思いつかないとなんともならないんだろうなあ。 それ…

Problem 367朝、なかなかつながらない。30分くらいして見たが、英語がわからない。昼に和訳を見てやっと意味が分かった。しかし、雲をつかむような問題だ。そのうち置換の性質を使えばできそうだと気づいた。ただ、今日はあまり考えている時間がない。

Problem 85前々回の方法だと計算量はだいたいO(N1/4)になります。だから、1032くらいが視野に入ってきます。ScalaはBigIntを使うと遅くなるので、型を決めるのは重要です。mはIntで十分です。nはLongが必要です。それから、sqrtですが、これは引数が大きくな…

Problem 85別の方法もあります。簡単のために長方形の数を100とします。三角数を並べます。 1 3 6 10 15 21 28 36 45 55 66 78 91 105これとこの逆の並び、 105 91 78 66 55 45 36 28 21 15 10 6 3 1とでマージ法を使います。先頭の1と105の積は105です。こ…

Problem 85m×nの長方形はm(m + 1)n(n + 1) / 4個の長方形を含みます。目標の長方形の個数をNとしてmを固定すると、 n2 + n + 1 = 4N / m(m + 1) となります。これを解いて、 n = (-1 + √(1 + 16N / m(m + 1))) / 2 これは一般に実数ではないので、[ n ]と[n +…

http://projecteuler.net/index.php?section=problems&id=366やっと728が出た。でも本番はここから。 やっとできた。43着。パッと見よりも易しかった。

Problem 83まずマスiからマスjへの遷移確率を求めます。（これが難しいのですが。Pythonなら書きやすいのに） その遷移確率行列Aは各マスに止まる確率をvとして次が成り立ちます。 Av = v すなわち、これは固有ベクトルを求める問題です。 ただ、固有ベクト…

http://projecteuler.net/index.php?section=problems&id=365小手先で速くしたら、5分半が49秒になった。でもこれ以上なにも思いつかない。

http://projecteuler.net/index.php?section=problems&id=365早起きして、問題を見て、それから初日の出登山へ。その途中にちょっと考えたらだいたいわかった。この問題の肝は数論のあの定理、なのかなあ。ただ、コード化するのがめんどうだった。そのほかに…