2011-01-01から1ヶ月間の記事一覧
http://projecteuler.net/index.php?section=problems&id=322 ダメだ。頭が痛くて働かない。寝不足なので、少し寝るかな。
Problem 14 コラッツです。単純に最初から順に長さを計算すると、3日くらいかかりそうです。
Problem 13 8桁ずつ区切って計算します。足し算なので簡単ですね。
http://projecteuler.net/index.php?section=problems&id=73 既約の分数の個数を求めるには、条件を満たす全ての分数の個数から既約でない分数の個数を引けばいいです。分母と分子の最大公約数が2で割り切れる分数は、分母が12以下とすると、 2/12 2/10 2/8 …
http://projecteuler.net/index.php?section=problems&id=73 PDFをさらに読み進めると、こんな解法が。 f(n)を値が与えられた範囲の分母がn以下の分数の個数、g(n)をそのうち既約の分数の個数とします。0から1の範囲でn = 12のとき、分母と分子の最大公約数…
Problem 12 エラトステネスのふるいのように約数の個数を求めるとさらに速くなります。ここの下のほうで説明した方法とだいたい同じです。ただし、下の段には素因数分解を記憶しておくのではなく、約数の個数を記憶しておきます。具体的には、まず1を代入し…
http://projecteuler.net/index.php?section=problems&id=321 M(3)が出ないんだけど。英語の読み方間違えてる? M(3)出た。やっぱり英語の解釈に問題があったようだ。 現状ではM(10)でも1時間近くかかりそう。 だいたいわかった。久しぶりにこのパターンか。…
Problem 12 1 2 3 4 5 6 …の偶数を2で割って、 1 1 3 2 5 3 …隣同士を掛け合わせると、 1 3 6 10 15 …これは三角数の列になっています。2番目の列の約数の数を求めると、 1 1 2 2 2 2 …隣同士を掛け合わせて、 1 2 4 4 4 …これが対応する三角数の約数の数に…
Problem 12 三角数をふつうに素因数分解していたのでは間に合いません。
http://projecteuler.net/index.php?section=problems&id=73 1/3と1/2の間に分母、分子をそれぞれ足して2/5があります。これは分母が5以下で唯一の分数です。1/3と2/5の間の3/7と2/5と1/2の間の3/8にも同様のことが言えます。再帰的に分数を数えることができ…
http://projecteuler.net/index.php?section=problems&id=73 PDFを見たら、小さい順に列挙すると書いてありました。なるほど、できそうだなと思って計算したら簡単にできました。しかし、遅い。
http://projecteuler.net/index.php?section=problems&id=320 二分探索なんて必要なかった。一発で求まるのだった。 しかし、あまり速くなっていない。どうやったら速くなるのか。
http://projecteuler.net/index.php?section=problems&id=320 S(1000)を出すのに1時間かかった。もう心が折れそう。実行時間30秒。 1.6秒になった。 結局47分かかった。14着。どうやったら速くなるんだ。 二分探索の範囲がいい加減だったのをちゃんとしたら1…
http://projecteuler.net/index.php?section=problems&id=73 今度は分子nを固定しましょう。1/3と1/2に入るには、分母dは2nと3nの間になります。ただし、3nは12000より大きくてはいけないので、nが4000以下ならφ(n)個の題意を満たすdがあることになり、そう…
http://projecteuler.net/index.php?section=problems&id=73 分母dに対して、互いに素になる分子nを指定した範囲で数えればよいです。オイラーのφ関数を使うとだいたいφ(d) / 6になるのですが、その差分の計算を以前書きました。この計算はわざわざ素因数分…
Problem 11 スペースで区切るコードを書きましょう。頭から見ていってスペースがあったら配列に登録するだけです。 rem // 引数は 文字列 配列変数 バッファ :split if %1 == "" ( call :push %2 %3 exit /b 0 ) set s=%~1 set c=%s:~0,1% if "%c%" == " " (…
http://projecteuler.net/index.php?section=problems&id=73 Problem 319、49時間で席が埋まりました。20時間の空白など、凶悪ぶりが際立ちました。さて、フォーラムによるとProblem 73が関係あるらしいです。そこでこの問題を改めて考察してみましょう。 1/…
http://projecteuler.net/index.php?section=problems&id=319 C++だと割り算の回数を減らすのが速度に効くはず。Pythonではほかが遅いので気にしないけど。工夫してみたら、2倍になった。思ったほど速くならなかった。それでも速いマシンで走らせたら7分にな…
http://projecteuler.net/index.php?section=problems&id=319 すっかり忘れていて4時間以上経ってから見たら、まだ正答者0。今日は夜中まで戦わないといけないのか? 素直に書いてみた。t(7)でも10秒かかった。 t(10)が出るようになった。85秒だけどもっと速…
Problem 11 与えられたデータをテキストファイルにしてそれを読みましょう。 @echo off for /F %%s in (%1) do echo %%s 08 49 81 …実は、%%sには1行そのままではなくスペースとタブで区切られた最初のトークンが格納されます。文字列全体を格納するにはオプ…
べき乗は、ふつうはバイナリ法を使うと速くなるのですが、バッチファイルの場合は事情が変わってきます。バッチファイルではforループが相対的に速いため単純に一つずつ掛けていくのが速くなりやすいのです。 @echo off set /a N = 100 set /a e = 128 call …
Problem 10 Miller-Rabin法を実装してみましたが、さらに時間がかかりました。しかも自乗でオーバーフローする問題に対処できていません。
Problem 10 Problem 7と同じように部分的にエラトステネスのふるいを行います。 しかし、2時間もかかってしまいました。この連載ではなるべくなら1時間以内で答えを出したいところなのです。
Problem 9 この問題は、実は手計算レベルです。直角三角形の辺の長さは表すと、 a = l(m2 - n2) b = 2lmn c = l(m2 + n2) 0 < n < m m + nは奇数 mとnは互いに素。 このとき周の長さは、 a + b + c = 2lm(m + n) よって、mとm + nは500の約数で互いに素。と…
http://projecteuler.net/index.php?section=problems&id=318 これもサービス問題。 こちらのほうが自分で計算しなくてすむ分簡単。
http://projecteuler.net/index.php?section=problems&id=317 すっかり忘れていた。 新春ということで、これはサービス問題。 ん、どこが間違っている? 計算間違えていただけだった。
Problem 8 数字の並びはテキストファイルにしておきます。実はバッチファイルはテキストファイルを読めるのです。 @echo off for /F %%s in (%1) do echo %%s これでテキストファイルを表示できます。これは1行ずつ読んでそれをスペースとタブで区切った最初…