2010-06-01から1ヶ月間の記事一覧

Project Euler 113

http://projecteuler.net/index.php?section=problems&id=113 これは単なる重複組合せですね。 N桁までとすると増加数は、 9H1 + … + 9HN = 9C8 + … + N-8C8 減少数は0も使えるから数が0になる場合だけ除いて、 10H1 + … + 10HN - N = 10C9 + … N+9C9 あと、…

Project Euler 112

http://projecteuler.net/index.php?section=problems&id=112 増加数と減少数を昇順に生成するのは簡単です。これを合成して非バウンド数を昇順に生成します。それと自然数を同時に生成すると、例えば90%のとき、 … 2176 2177 2178 2179 2180 … … 21100 2111…

Project Euler 111

http://projecteuler.net/index.php?section=problems&id=111 単純に、対象となる整数を生成して素数判定します。生成は、例えば4桁で1を3つ使うとすると、残りの1つの桁をまず決めて、そこに1以外の数字をあてはめます。素数判定は、単純に素数で割っていき…

Project Euler 110(2)

http://projecteuler.net/index.php?section=problems&id=110 例えば解の個数が100より大きい最小の自然数を考えるとすると、重複を入れて201個以上が必要です。最も大きな素数を使う場合を考えると、各指数が1なので、35 = 243だから、 21・31・51・71・111…

Project Euler 298

http://projecteuler.net/index.php?section=problems&id=298 1時間半で5人できていた。それから問題文を読もうとするが、眠くてなかなか頭に入ってこない。いちおう理解したつもりだが、どう手をつけていいのかわからない。 たぶん目途立ったけど、うまく動…

Project Euler 110(1)

http://projecteuler.net/index.php?section=problems&id=110 n = p1e1…pmem とすると、解の個数は、 ((2e1 + 1)…(2em + 1) + 1) / 2 なので、指数のみで決まります。例えば、2e1・3e2と2e1・5e2では、解の個数は同じでも前者の方が小さくなります。また、23…

Project Euler 108

http://projecteuler.net/index.php?section=problems&id=108 (x - n)(y - n) = n2 だから、nを素因数分解して、 n = p1e1…pmem とすると、解の個数は、 ((2e1 + 1)…(2em + 1) + 1) / 2 となります。 単に割っていって素因数分解するのは遅いので、エラトス…

Project Euler 109

http://projecteuler.net/index.php?section=problems&id=109 最後を除いて、重複を避けるためにすべてのポイントを並べて前から順に取っていきます。

Project Euler 107

http://projecteuler.net/index.php?section=problems&id=107 点と辺から成る数学対象をグラフといいます。辺に重みがついているとネットワークと呼びます。辺を一つでも取り除くと複数の繋がっていない部分に分かれてしまうグラフを木といいます。木はルー…

Project Euler 103(2)

http://projecteuler.net/index.php?section=problems&id=103 このシリーズの最後に、この問題をチェックする集合のペアを減らして解きましょう。 n = 7なら要素数2つずつまたは3つずつの集合のペアについてチェックすればよいです。チェックするペアはあら…

Project Euler 106(2)

http://projecteuler.net/index.php?section=problems&id=106 前回は集合のペアを生成してチェックしなければならないかどうか判定しましたが、チェックしなければならない集合のペアを直接生成できないでしょうか。これは難しそうですが、逆にチェックしな…

Project Euler 297

http://projecteuler.net/index.php?section=problems&id=297 最初、問題取り違えてた。 ちょっと考えれば簡単。メモ化使って3msecだった。

Project Euler 106(1)

http://projecteuler.net/index.php?section=problems&id=106 まず、可能なBとCの組合せの数を数えておきましょう。まずBを一つ以上選びます。そして、残った中から一つ以上選びます。 nC1(n-1C1 + … n-1Cn-1) + … + nCn-11C1 = nC1(2n-1 - 1) + … + nCn-1(2…

Project Euler 105

http://projecteuler.net/index.php?section=problems&id=105 Problem 103と同じ判定を適用するだけです。

Project Euler 103

http://projecteuler.net/index.php?section=problems&id=103 まず、問題文にある「ルール」に従って集合を作ります。n = 6の例を参考にして、各要素を-2〜+1しかつ昇順を崩さない集合を作ります。それが題意を満たすか調べます。2つ目の性質を調べるのは簡…

Project Euler 104

http://projecteuler.net/index.php?section=problems&id=104 pandigitalかどうかの判定は、各桁の数字を用意して、それを整数の各ビットに見立てて1〜9で和を取ると、 21 + 22 + ... + 29 = 1022 となるので、これで判定できます。 下9桁の数字を出すのは、…

Project Euler 102

http://projecteuler.net/index.php?section=problems&id=102 高2くらいで習うベクトルの計算をするだけです。

スマートポインタ

以下は、VC10 beta2で確認した。 よくあるコードでコンテナにオブジェクトのポインタを入れることがあります。このとき、コンテナのデストラクタを呼ぶ前にポインタの差すオブジェクトのデストラクタを呼ばなければなりません。しかし、これはよく忘れます。…

Project Euler 101

http://projecteuler.net/index.php?section=problems&id=101 これは、線型方程式を解くだけなので簡単です。 しかし、これって必ず整数になるのでしょうか。重ね合わせの原理が効くので単項式だけ考えればよいのです。Vandermonde行列がでてきます。10乗ま…

Project Euler 50

F#

http://projecteuler.net/index.php?section=problems&id=50 どうしても素数列の遅延評価ができない。

Project Euler 296(2)

http://projecteuler.net/index.php?section=problems&id=296 やっとBEの式が求まった。幾何は苦手。 こっからどうやるんだっけ? Pythonでふつうに組んだら2時間以上かかりそう。 C++で組んだら6分。高速化はあとで考えよう。 20時間経っているのに24人しか…

Project Euler 296

http://projecteuler.net/index.php?section=problems&id=296 図形の問題。 20分でBEがだいぶ簡単になったけど、ここから問題解けるのかなあ。

Project Euler 49

F#

http://projecteuler.net/index.php?section=problems&id=49 重複組合せで数字を出して、題意を満たすか調べます。

Project Euler 48

F#

http://projecteuler.net/index.php?section=problems&id=48 多倍長整数を使うと簡単すぎるので、64ビット整数を使って、5桁で区切って掛け算を行いました。

Project Euler 295(5)

http://projecteuler.net/index.php?section=problems&id=295 今の解き方は前段と後段があって、最初後段は前段の10倍以上かかっていたが、工夫して前段より速くなった。そこで前段を少し見直したら10倍くらい速くなった。これで24分。 後段はまだ何か手があ…

Project Euler 47

F#

http://projecteuler.net/index.php?section=problems&id=47 素数関係のコードをいちいち書いたりコピペするのが面倒なので、別ファイルにします。そのときに、名前空間とモジュールを使います。 // mod1.fs namespace NS1 module Mod1 = let a = 1 // mod2.…

Project Euler 295(4)

http://projecteuler.net/index.php?section=problems&id=295 出来た。 色々工夫して高速化したのだが、それでもPythonで2時間半かかった。 どうやら大半は与えられた2次方程式に整数解があるか調べるところに時間がかかっているようだが、sqrtだけにかかっ…

Project Euler 295(3)

http://projecteuler.net/index.php?section=problems&id=295 結局、どう重複を回避するかで、なんとかメモリを食わないアルゴリズムを思いついたが、Pythonはこの手の計算が遅くてどうしようもない。今のままだと何時間もかかる。 C++で書き直そうかな。

Project Euler 295(2)

http://projecteuler.net/index.php?section=problems&id=295 おかしいな、L(10)すら出ない。 本当に何を見落としているのかわからない。イメージしにくいのでExcelで図を描いてみたが、それでもわからない。 あ、L(10)はわかった。でも、L(100)はわからない…

Project Euler 46

F#

http://projecteuler.net/index.php?section=problems&id=46 これも前問と同じアルゴリズムを、奇数ごとに適用します。この問題は有限リストなので素直に書けます。