2009年2月5日木曜日

Project Eulerを150問解いてみた

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

最近、Project Eulerを再び解き始めた。8ヶ月以上のブランクだ。前回の最後にGoogle App Engineの招待状が届かないと文句を言っていたのだが、その後、すぐに届いてそちらの方にはまってしまった。で、Project Eulerについてはそのまま忘れてしまっていた。

再開してみたはいいが、ブランクがあったせいなのか、いまいち頭の回転が落ちたように感じる。問題がなんだか難しく感じるのだ。それとも以前よりも本当に問題が難しくなっているのだろうか。何はともあれProject Eulerは頭の体操には持って来いだし、最近いじっていないC++を錆びつかせないようにするのにも役立っている。とは言ってもクラスの設計が必要なほど大規模なプログラムにはならないけど。

現在、230問中150問解き、やっとレベル4になった。日本人の中では515人中24位。10日間ほどで30問弱を解いたが、このペースだと疲れる。もう少しゆっくり解こう。

問題114は、ブロックを組み合わせる問題。組合せの関数とハッシュで実行時間は一瞬。

問題115も、ブロックの組み合わせ。問題114が解ければ問題なし。

問題116も、問題114/115の類似問題。

問題117も、ブロックの組み合わせの応用。問題なし。

問題121は、順列を用いた関数を作って対処。実行時間は一瞬。

問題122は、掛け合わせが最も少ない組み合わせを探すアルゴリズムを考えるのがちょっと面倒だった。改良の余地があると思う。実行時間は約25秒。

問題124は、因数を使って解く。正解者も多く、簡単だと思う。

問題125は、素直に調べた。実行時間は一瞬。正解者は多め。

問題126は、立体図形の問題。キューブの増え方の規則が分かれば解ける。図形問題は好みだなぁ。実行時間は一瞬。正解者は少なめ。

問題127は、最小公倍数に関する問題。ちょっと苦労した。実行時間がかかったので改良の余地あり。

問題128は、効率の良いヘックスタイルの生成関数を作れば解ける。これは面白かった。実行時間は約1秒。

問題130問題132問題133は、レピュニット(repunit)に関する問題。苦労した。これは苦手だ。あと、問題129もレピュニットに関する問題だがまだ解けていない。

問題131は、素数に関する問題。与えられた式をいじって素数候補を絞った。実行時間は一瞬。

問題134は、素直に計算した。もっと効率的なアルゴリズムがあると思う。

問題135は、式を変形させ計算量を減らし解いた。それでも少し実行時間がかかったので改良の余地あり。

問題136も、式を変形させて計算量を減らした。式の変形は解法の基本かな。実行時間は約8秒。

問題137は、10番目まで出力させ、それらの数列から規則を見つけた。

問題138は、図形問題だが実は問題137と似ている。規則を見つけよう。

問題139も、問題137/138と類似している。少し複雑になっているが大したことはないと思う。

問題140は、完全に問題137の応用。規則を見つければ良い。

問題141は、数が大きくて、計算量を減らしたつもりだったが時間がかかった。改良の余地あり。

問題142は、式を変形させて解いた。実行時間は約40秒。もう少し改良できるかも。

問題143は、三角関数を使って解いた。最初、問題文を読み違えて苦労した。計算量を減らすためにやや工夫したが、それでも計算時間は6分半ほどかかった。正解者はかなり少なめ。

問題144は、素直に入射角と接線から反射角を求め、それと楕円との交点の計算を繰り返して解いた。計算時間は一瞬。

問題145は、普通に数え上げた。もっと良い方法があると思う。正解者は多め。

問題148は、シンプルだけど醜いコードになった。気分的にすっきりしないなぁ。実行時間は約3秒。

問題173は、正解者が多いだけあって簡単だった。実行時間は2秒弱。

問題187は、普通に数え上げた。正解者は多め。

0 コメント: