2011-12-01から1ヶ月間の記事一覧

ScalaでProject Euler(121)

Problem 83ダイクストラ法への道 第3弾です。いよいよダイクストラ法を使います。 131 673 234 103 18 201 96 342 965 150 630 803 746 422 111 537 699 497 121 956 805 732 524 37 331最後は右と左と下と上の隣のマスへ進めます。まず左上のマスは確定です…

ScalaでProject Euler(120)

Problem 82ダイクストラ法への道 第2弾です。 131 673 234 103 18 201 96 342 965 150 630 803 746 422 111 537 699 497 121 956 805 732 524 37 331今度は右と下と上の隣のマスへ進めます。左の列から順に考えていきます。最も左の列は上から下への経路しか…

ScalaでProject Euler(119)

Problem 81ダイクストラ法への道 第1弾です。 問題に載っている例で考えてみましょう。 131 673 234 103 18 201 96 342 965 150 630 803 746 422 111 537 699 497 121 956 805 732 524 37 331左上をスタートして動けるのは右と下だけです。左上から各マスへ…

ScalaでProject Euler(118)

Problem 80この問題は整数で考えるとよいです。すなわち、2ならこれに0を198個つけた整数200…00の平方根を整数で考えます。そうするとそれはちょうど100桁になり各桁を足し合わせればよいことになります。平方根を整数で考えるというのは例えば24なら4、25な…

Project Euler 364(2)

http://projecteuler.net/index.php?section=problems&id=364逆元をエラトステネスのふるい的に求めたらその部分は56倍の速度になり全部で8秒になった。その他、いろいろ速くして3.5秒になった。まだ速くなりそう。

Project Euler 364

http://projecteuler.net/index.php?section=problems&id=364土曜の夜、いちおう問題見たんだけど、なかなか考える時間が無くて。誤読してるし。昨日の帰りに考えたら地道に組めばいいだけだとわかったので、組んでみた。T(1000)までは出たが、それ以降は帰…

ScalaでProject Euler(117)

Problem 793桁のキーの前後の数字を関係付けます。例えば319なら、3 → 1、1 → 9という辺をグラフに加えます。そうしたときに、グラフの辺の始点側になっていない点が一つあります。これが元の数の最も右の数字です。そして、この数字を終点とする辺をすべて…

Project Euler 363(2)

http://projecteuler.net/index.php?section=problems&id=363やっとできた。面積を求めるところがおかしかったから、別の時間がかかる方法でやった。といっても100秒だった。もっと早くやればよかった。加速法を使えばもっと速くなるかな?しかし、何が間違…

Project Euler 363

http://projecteuler.net/index.php?section=problems&id=363きのう遅れて帰ってきたがなかなかつながらず。つながってもJavaが動かない。忙しいので無視して今朝問題見たら、高校数学に毛が生えた問題に見える。 さっき組んでみたが、incorrect。どこが悪い…

ScalaでProject Euler(116)

Problem 78分割数p(k)には、実は次のような漸化式があります。 p(k) = p(k - 1) + p(k - 2) - p(k - 5) - p(k - 7) + p(k - 12) + p(k - 15) - … p(0) = 1 p(k) = 0 (k 漸化式のpの中のk - mのmは五角数になっています。符号は、+ + - - + + - -となります。…

ScalaでProject Euler(115)

Problem 77前問とほとんど同じです。再帰に持ち込んでメモ化です。

ScalaでProject Euler(114)

Problem 76f(n, m)は同じ引数で何度も呼び出されます。例えば、f(1, 1)は169229875回呼ばれるようです。fは引数が同じならいつも同じ答えを返すので、それを記録しておけばよいです。メモ化ですね。これで3msくらいです。本当はもっと速い方法があるのですが…

ScalaでProject Euler(113)

Problem 76Project Eulerには再帰に持ち込めば簡単になる問題が多いです。5を分割することを考えます。まず5から4を取ります。残り1なのでその分割数を考えればよいです。次に5から3を取ります。残り2なので2の分割数を取ります。次に5から2を取ります。残り…

Project Euler 362(3)

http://projecteuler.net/index.php?section=problems&id=362答えだしたら合ってた。36着。 でも、5分もかかった。Pythonでどうやったら速くなるんだろう。

Project Euler 362(2)

http://projecteuler.net/index.php?section=problems&id=362今日の昼休みに手計算でS(100)を求めていたらだんだんわかってきた。素数を求めるのにも1時間以上かかるのにと思っていたが、全然見当違いだった。でも1分以内は無理かな? え、1010までのsquare …

Project Euler 362

http://projecteuler.net/index.php?section=problems&id=36243分も経って、そういえば16時に出題だと気が付いた。まだ誰も解けていないようだった。また解けなそうだ。やっとS(100)出た。でも1010は厳しそう。S(106)で9秒もかかっている。

Project Euler 149

昨日、アルゴリズマーのためのゴルフのススメを読んで、帰宅ジョグのときに最初の問題を考えた。そういえばProject Eulerにもこんな問題あったなあ。でも前は解ければいいってことでO(n2)にしっちゃったのかなあ。こういうのってO(n)ってわかってると思いつ…

ScalaでProject Euler(112)

Problem 75 a = 2lmn b = l(m2 - n2) c = l(m2 + n2) (m, n) = 1 m + nは奇数 に従えば簡単に直角三角形が列挙できるので、それで長さについてカウントしていくだけですね。

ScalaでProject Euler(111)

Problem 74大きさ100000の0に初期化した配列を用意します。 例えば、69を考えます。このインデックスの配列の要素を-1とします。69の次は363600です。ここは-2とします。次の1454は-3とします。このように進んでいくと、1454がやってきます。ここは0でなく負…

ScalaでProject Euler(110)

Problem 73対象を1/3より大きく1/2より小さいより、1/3以下とするほうが考えやすそうなのでそうしましょう。1/2より小さいは、前問の1より小さいから1/2の1個を引いて半分にするだけです。例えば、d = 40で考えましょう。取りうるnは1〜13です。ここから2の…

ScalaでProject Euler(109)

Problem 73単にその範囲の分数を列挙して分母分子が互いに素なものを数えるだけで1秒以内でした。

Project Euler 361

http://projecteuler.net/index.php?section=problems&id=361久しぶりにスタンバイした。 問題の意味がわからない。ああ、分かった。18分経ってわかった。 A1000出た。しかし、まったく手がかりがつかめない。 固有名詞が出ているので、それで調べてみた。T…

ScalaでProject Euler(108)

Problem 72dを固定して考えましょう。例えば10とか。nで取りうるのは1〜9です。しかし、nとdは互いに素なので、結局とりうるのは 1 3 7 9の4つです。これはφ(10)です。定義そのものですね。したがって、 φ(2) + φ(3) + ... + φ(1000000) を計算すればよいで…

ScalaでProject Euler(107)

Problem 71N = 1000000として、分母がN - 6以上だけを考えればよいです。なぜなら、分母がN - 7以下のとき、a / bとして、(a + 3) / (b + 7)のほうが3 / 7に近いからです。

Project Euler 360(4)

http://projecteuler.net/index.php?section=problems&id=360フォーラムの方法で雑に組んだら確かに20秒になった。明日こそPriorityQueueを使ってみよう。

PriorityQueueで比較法を指定する

Problem 70はフォーラム向けにまずPythonで解きました。そのとき、最初はPriorityQueueにつっこむ値をdoubleにしていました。しかし、これは正確ではありません。doubleで表現すると同じ値でも実は違う値ということもあり得ます。もっともそれが両方とも並べ…