2008年5月12日月曜日

Project Eulerを100問解いてみた

このブログ記事をはてなブックマークに追加

相変わらずProject Eulerを解いている。これまでは連続して問題を解いていたのだが、今回からはバラバラになってしまった。別に途中に解けない問題があったわけではなく、後半の問題を眺めたところ面白そうな問題が目に付いてしまって、それに手を付けてしまったのだ。具体的には問題188のテトレーションの問題。以前、ここのブログでも虚数のテトレーションというテーマでテトレーションを扱ったことがある。そこで、i がある値に収束するのを発見したのだが、何か意味があるのあるのかな?

今回から順番を気にしないことにしたが、だからと云って簡単そうな問題ばかり手をつけても面白くない。どうせなら一番難しいそうな問題を解いてみようということで、問題177を解いてみた。最近追加された2問を除くと、正解者が100人を切っている唯一の問題だ。自分が解いたときは全体で87番目の正解者だった。一番難しそうな問題を解いて今後の弾みにしようかと考えていたのだが、このレベルの問題ばかりだとさすがにへこたれそうだ…。

現在、193問中100問を解いた。世界ランクで24217人中608位。日本人の中では235人中20位。

問題81問題82問題83はすべてダイクストラ法であっという間。ダイクストラは偉大だ。

問題84は、モノポリーで止まるマスの確率を求める問題。そんなに難しくないけど、正解者は少なめ。面倒だからかな。

問題85は、マスに填まるすべての四角形を数え上げる問題。普通に数えれば解ける。

問題86は、ちょっと考えたけど、解き方がわかれば計算量は僅か。正解者少なめ。

問題87は難しくない。調べる数はそれほど多くないことに気づくはず。

問題89はそんなに難しくないはずなのだけど、間抜けなところでちょっとはまった。IIXが8であると疑わなかったよ…。

問題91は、まともに全部数え上げた。もっと効率のよい方法があると思う。

問題92は簡単。

問題94は結構苦労したな。計算時間が長かった。これはもっと改良せねば。ピタゴラス数を普通に使うだけではダメだ。

問題97は簡単。この手の問題はどれもそうだけど、最後の必要な桁数だけ計算すればよい。

問題99は簡単すぎる。log使え。

問題100はちょっと悩んだ。いろいろいじっているとある数列が浮かび上がったので、それをもとに解いた。有名な数列みたい。

問題101は、問題を把握するのが面倒だった。連立一次方程式を解けば良い。行列演算使えば簡単。SciPyは偉大だなぁ。誤差には注意。

問題102は簡単。なはずなんだけど思ったより時間がかかった。高校数学やり直しだな、こりゃ。

問題112は、問題文が分かりにくかったな。要は数字が降順でも昇順でもない数を数え上げるだけ。

問題123は、Pythonで楽して解いた。

問題177は難問かと。細心の注意が必要なので、自分のように疲れている時にやらない方が無難。一日かかったよ。考え方自体はすぐに浮かんで実際それで正しかったのだけど、適当にコーディングするとはまる。

問題188は、一連の問題を順不同に解く切っ掛けとなった問題。テトレーション(tetration)を扱っている。なんていうかテトレーションにはロマンのようなものを感じる。変?

それにしても最近はProject Eulerばかり扱っているな。本当はGoogle App Engineなどもいじりたいのだけど、未だに招待状が来ない。アプリはいくつか作っているのに…。いい加減、やる気が削がれるなぁ。

写真は問題を解いたときのメモ書きの一部。ペンと紙さえあればなんとかなるかも?

0 コメント: