Project Eulerを120問解いてみた

ちまちまとProject Eulerを進めているが、さすがにペースが落ちている。今回は問題88が難しかった。しかし、同じように難しかった問題177と違って、いろいろとアルゴリズムを考え出して最後にスパッと解けたので気持ちがよかった。問題177は最初にやり方はわかったけど、途中の組み立てとフィルターに苦労したので解けたときの充実感よりも疲れのほうが大きかった。

ここまで1ヶ月弱かぁ。結構かかるなぁ。現在、195問中120問解いた。世界ランクで24451人中387位、日本人の中では257人中15位。

問題88は、今回もっとも苦労した問題だ。最初はまともに数え上げようと思ったが、それではまったく埒が明かないことにすぐ気付き、別の方法を考えることに。4～5つのアルゴリズムを考え、最後に思いついた方法でやっと解けた。実行時間約8秒はまあ許容範囲だろう。

問題90は組合せの問題。条件が少し変わっているけど、それに気をつければ問題ないかな。

問題93は逆ポーランド記法を使って解いたのだけど、何故か解が二つに。一方が正解だったのだけど、どこか間違えたかな? フォーラムにも自分と同じ結果になっている人がいた。

問題95は100万まで考えるのが大変だったので途中までの解を入れたら正解だった。後でフォーラムで勉強しておこう。

問題96の解き方はすぐに浮かんだけど、実装がちょっと面倒だった。実行時間は約3秒。

問題98は最初にペアグループを作ったけど、ペア自体はそんなに多くない。アナグラム解析は力技で約20秒。

問題103はあるルールに従った数のグループを扱う問題。問題105と問題106も同様の問題。これは力技で解いたので実行時間がかかった。この解き方では問題105と106は難しい。

問題104はPythonで解いた。でかい数を扱うときはPythonがやはり楽。頭とおしりだけを考えればよい。

問題105は問題103と同様の問題。与えられた数列がルールに従っているか調べる。良さそうなアルゴリズムを思い付いたので実行時間は短かった。

問題106は問題103をもう少し難しくしたもの。問題105で使ったアルゴリズムで1秒かからなかった。

問題107は最小木問題。アルゴリズムを知らなかったのでちょっと苦労した。

問題108はアルゴリズムを考え付くまでちょっとかかった。同種の問題110より簡単な問題。

問題109は正解者が少なめだから気合を入れて臨んだが簡単だった。問題文が長いから敬遠しているのかな。

問題110は苦労した。ある程度推測を立ててやらないと解けなかった。

問題111は計算時間が結構かかったかも。

問題113はハッシュで解いて15ミリ秒で解けたと喜んでみたけど、単なる組合せの問題だと知ってショック。

問題118は順列で解いた。約6秒なので許容範囲か。

問題119はPythonで素直に解いた。約1秒。

問題120はある規則を見つければそんなに難しくない。

問題185は解いたは解いたけど実行時間1時間以上ってのは酷すぎる。フォーラムで勉強しよう…。