Project Eulerを問題80まで解いてみた

Project Eulerを前回からちまちまと続けている。連休中は忙しくてあまりできなかったが、それでも合間合間の時間を使って紙と鉛筆でも考えることはできるので、頭の体操にはちょうど良い。前回、結構簡単だと書いたのだが、50問を超えるあたりから難しめの問題が入ってきた。一つ解くのに30分以上かかることもざらだ。計算自体はすぐに終わるのが多いが、いくつかは結構時間がかかってしまった。特に問題60では10分弱かかかってしまう。フォーラムなどを読むと、1秒かからない人もいるので、やはりアルゴリズムが決定的だ。現在192問中80問を解いた。

問題51は素数に関わる問題だけど、数字をいじる問題は結構好きかも。

問題52は数字の並べ替え。

問題53は組み合わせの問題。これは簡単かな。

問題54はポーカーの勝敗判定のプログラム。この手のコードはよく組むけど好きなわけではない。面倒なだけで難しくはない。

問題55も数字をいじる問題。

問題56は数がでかいが、ただそれだけ。

問題57は連分数に関する問題。連分数に関する問題の中では序の口。

問題58は結構数が大きくなった。

問題59は簡単。

問題60は素数で数字を操作する問題なので結構好きだ。でも解くのは結構大変だった。

問題61は素直に解くだけ。

問題62は普通に解いたかな。数字系。

問題63は簡単だった。

問題64～66までは連分数に関する問題。連分数は頭が疲れる…。

問題66が連分数に関する問題なのを知ってちょっと面白かった。

問題68は解いている人がこのあたりの問題の中では少ないから難しいのかと思ったら簡単だった。何も特別なこともしていないし何でだろう? 因みにこの手の図形的な問題も好み。

問題69～73まではオイラーのφ関数に関する問題。解き方がわかればそんなに難しくはないかも。わからないと時間が足りない。

問題74は簡単だった。

問題75はピタゴラス数の問題。解き方はわかったのだけど、変なところでバグをつぶすのに手間取った。

問題76は苦労した。計算時間も結構かかった。フォーラムで知ったのだが、Partition Function P(分配関数)による解法があるようで、これ使ったら一瞬で終わった。凄い。

問題77は76の応用。だけど、76で自分で考えた関数だとコードをほんのちょっといじるだけで解けた。計算時間も一瞬。個人的には76より簡単だった。

問題78も分配関数の問題。これ、計算時間的に結構大変なのですぐに解ける別の方法があるのかと考えたのだが、結局力技で解いた。

問題79は簡単。

問題80は開平法を使うだけ。

ここまでは虫食いになるのがいやで順番に解いてきたが、そろそろ難しくなってくるかも。まだ半分も行ってないしなぁ。今までのところ、前回同様にC++メインで解いている。でかい数字が面倒な時だけPythonかな。GMPあたりを使えばよいのだろうけど、何となく標準ライブラリにこだわっている。