2013-01-01から1年間の記事一覧

Project Euler 452

http://projecteuler.net/index.php?section=problems&id=45217着。26秒。 こういう問題になるとPythonというかLL言語は威力を発揮する。剰余は最後に取ればいいのだ。まともに計算してもたったの200桁あまり。これをきちっと剰余取りながら計算しようとした…

Project Euler 226

Problem 226この曲線は高木曲線としても知られています。高木とはもちろん高木貞治のことです。 この問題を解くにあたり、連続性と微分不可能性についての証明を考えたのですが、めんどうなのでここには書きません。 フォーラムに書きました。

Project Euler 314

http://projecteuler.net/index.php?section=problems&id=314326着。27秒。 ついにパーフェクトを達成した。ずっと問題を読み間違えていた。というかたぶんロクに読んでいなかった。月曜の夜寝る前になんとなく和訳を読んでみたら完全に間違っていたことに気…

Project Euler 451

http://projecteuler.net/index.php?section=problems&id=45185着。15分。 日曜はうまく書けず、今朝ジョギングしながら考えを整理した。 帰ってから書いてみたら、PyPyで2分くらいかかりそう。しかし、実際に動かしてみるとメモリが足りない。Pythonでも足…

Project Euler 450

http://projecteuler.net/index.php?section=problems&id=45023着。1秒。 日曜は何も思いつかなかった。 月曜の朝に、実はこの問題はそんなに難しくないことに気が付いた。 この問題は2つの部分に分けることができる。月曜の夜に半分をなんとか書いた。まだ…

Project Euler 227(3)

Problem 227 フォーラムに書きました。

Project Euler 449

http://projecteuler.net/index.php?section=problems&id=44930着。 スタンバイしたが許された時間は1時間半。一瞬楕円体から楕円体を引くだけなんじゃ、と思ったが、さすがにそれはない。少し考えればそれではダメなことがわかる。しかし、これを解くにはど…

Project Euler 448

http://projecteuler.net/index.php?section=problems&id=44813着。90秒。 出かけていて電車の中でコーディングだけして、あとは帰ってPCで動かすだけだった。帰って動かしつつログインしようとするが入れない。何度やってもダメ。TLを見てみると、7人しか正…

Project Euler 447

http://projecteuler.net/index.php?section=problems&id=44736着。99秒。 わかってしまえばなんということもなかった。 この問題は前の2問とは解き方が違う。わからなければ一歩前に戻ればいい。 久しぶりに週末に終われなかったが、結果的に3問とも50位以…

Project Euler 446

http://projecteuler.net/index.php?section=problems&id=44631着。 こっちの方が簡単。n4 + 4は高校数学を思い出すだけ。 ふつうに書くとメモリが足りないが、ちょっとだけ工夫したらギリギリ足りた。

Project Euler 445

http://projecteuler.net/index.php?section=problems&id=44540着。Pythonで6分もかかった。PyPyは遅かった。 いつもと違う特殊なことをして手間取った。ふつうに書くとO(N^2)になってしまう。

Project Euler 444

http://projecteuler.net/index.php?section=problems&id=44431着。0.7s。 前段は、電車の中で考えようと思ったけど、アメリカの尻拭いのせいか、やけに混んでいて無理だった。昼食で定食を食べているときにノートに計算していたらわかった。後段はまったく…

Project Euler 220(2)

Problem 220 forumに書きました。

Project Euler 443

http://projecteuler.net/index.php?section=problems&id=44362着。 朝起きて問題見たらすでに54人も解いていた。超Easy問題はいつもこの時間に出ているような気がする。 この問題は実験してみるとわかる。 Pythonで16秒、PyPyで3.4秒だった。

Project Euler 328

http://projecteuler.net/index.php?section=problems&id=328267着。 春ごろに見直して、これは再帰的な問題だろうと考えていたら、そのうちに解法がわかった。しかし、なかなか実装がうまくいかない。折れ線の関数を考えるのだが、その演算が合わない。暇な…

Project Euler 442

http://projecteuler.net/index.php?section=problems&id=44252着。 昨日問題が出てすぐに解法を思いついた。ただ実装が大変だ。2/3くらい書いて早めに寝た。今朝起きて残りを書いて、E(10000)とかがナイーブな実装と合っていることを確認してE(1018)を計算…

Project Euler 352

http://projecteuler.net/index.php?section=problems&id=352344着。40分。2年ぶりに解けた。 昨日の朝、ちょっとの時間で問題を見直すために、和訳が無いか検索したら和訳サイトが復活していた。それを読んで電車の中で考えたら、簡単なことに気が付いた。…

Project Euler 441

http://projecteuler.net/index.php?section=problems&id=44124着。 これはProject Eulerに典型の問題。初期からのパターンだ。そう思って考えるとすぐにわかった。しかし、なかなかバグが取れない。N=10で地道にデバッグした。5時間近くかかってやっとたど…

Project Euler 440

http://projecteuler.net/index.php?section=problems&id=44041着。 T(n)を計算するのは簡単。しかし、それらのgcdを計算するのは難しい。とりあえず実験をするのだが、ネットブックで計算するしかなく、なかなかちゃんとはわからない。それでもなんとか突き…

Project Euler 439(2)

http://projecteuler.net/index.php?section=problems&id=439速くする方法がわからないのでフォーラムを見て、なんとか完全理解した。 自分で組んで全桁出したら、PyPyで3分半だった。 しかし、要所要所で9桁にしてもあまり速度は変わらなかった。よくあるこ…

Project Euler 439

http://projecteuler.net/index.php?section=problems&id=43924着。 月曜の帰りにだいたいわかって、火曜の朝にごり押しできる式を見つけた。火曜の夜にコードを書いたが、PyPyで10時間くらいかかりそう。そこでC++で書き直したが、それでも4時間くらいかか…

Project Euler 438(2)

http://projecteuler.net/index.php?section=problems&id=438少し変えて20倍くらい速くなったので、フォーラムに書きこんだ。http://projecteuler.net/thread=438#136498

Project Euler 438

http://projecteuler.net/index.php?section=problems&id=43834着。 とにかく多次元なので頭の中で想像がつかなくて最初はヒューリスティックな方法を考えていたが、どうもうまくいかず。月曜に昼食をとり考えながら方法で結局最後まで押し切った。Pythonで…

Project Euler 437(2)

http://projecteuler.net/index.php?section=problems&id=437pを法として2乗するとnになる整数を求めるアルゴリズムがあるのでそれを使い、あとちょこちょこと直したら、57秒になった。

Project Euler 436(2)

http://projecteuler.net/index.php?section=problems&id=436区間を1/Nの幅で分割して近似していて、区間をたくさん飛んだ方が大きいとしていたが、実際には一番大きく区間を飛ぶのはそれより一つ小さく飛ぶのとかぶっていて、それを考慮するとN = 128で収束…

Project Euler 437

http://projecteuler.net/index.php?section=problems&id=43774着。 今朝電車の中で組んだが、ネットブックでは力不足。 夜帰ってきてから動かしてみると、メモリが足りない。多倍長整数を使っているからだ。そこはふるいなので、部分ふるいを使ってみる。ま…

Project Euler 436

http://projecteuler.net/index.php?section=problems&id=43697着。 平日組む時間がなくて、昨日電車に乗っている少しの間にコードを書いたが、なぜか1/2に収束する。 今日電車の中で437のコードを組んで、そのあとにノートを見ていたらミスに気付いた。 近…

Project Euler 426

http://projecteuler.net/index.php?section=problems&id=426121着。 あんなに考えたのに、実は単に検索すればよいだけの問題だった。そして、ナイーブに書くとO(N^2)だが、ちょっとデータ構造を工夫すればほぼO(N)となり、PyPyで2.6sだった。

Project Euler 435

http://projecteuler.net/index.php?section=problems&id=43592着。 Project Eulerはだいたい問題を90度違う角度から見るとよい。しかし、この問題は違う。素直に解けばよいだけ。ただ、Project Euler頻出のテクニックは要る。

拡張Pell方程式の解(2)

Pell方程式の初期解は、連分数から求められます(ペル方程式(2)参照)。拡張Pell方程式の初期解があるときは、この連分数がPell方程式の初期解が求まる前に求められます。D = 5でやってみましょう。 √5 = 2 + (√5 - 2) = 2 + 1/(√5 + 2) = 2 + 1/(4 + (√5 …