先週火曜日からProjectEulerに参加し始めた。
Project Euler(公式)
Project Euler問題和訳Wiki
ちなみに使用言語はSchemeで、現在の解答数はこんな感じ。
どの問題も、パワープレイで解けないことはないが、数学を活用すればスマートに解ける、この快感がたまらない。そんなわけで寝ても覚めても最適なアルゴリズムを考えている始末。
そんな状況なので、ProjectEulerの問題について何がしか書きたいと思ってしまうのが人間のサガというものだが、解法やそれに類することを書くのはProject Eulerの趣旨に反する。
（ネットで「ProjectEuler」ってけんさくすると、ソースコードをこうかいしてるひとがいるよ？ それってよくないよね！ ぷんぷん！ みんなもそういうサイトはみちゃだめだよ！）
そんなわけで、自分の回答状況、採った戦略などを、ネタバレ無しで、なんとなく、ぼかして、書いておくことにする。それでもヒントになってしまうかもしれないので、見る人は自己責任で。
それから、もしこれを読んで興味を持ったら、ぜひProjectEulerのサイトで問題を確認して、ついでに参加してみてほしい。プロコンと似てるかもしれないけど、数学に重点を置いているので、まずは紙と鉛筆で問題に取り組むことになるし、それはつまりいつでもどこでも気が向いたときに問題を解き始めることができる、ってことなのでとっても気楽なのだ（逆にいつでも問題に頭を悩ます、ということにもなるのだが……）。
（以下スクロールアウトのための余白。ヒントめいたものは一切読みたくない人向け。）
＊
＊
＊
では回答状況と基本戦略を。
Problem.1 ... solved.
手計算で解ける。
Problem.2 ... solved.
単純にフィボナッチ数列を計算するならパワープレイ。でも法則性を見つけるとスマート。
Problem.3
素数表作って総当たりで割っていけばパワープレイで解けるか？ 他にもっとスマートな方法が無いか考え中……いや、素数が関わる問題だからパワープレイが正解かもしれない。
Problem.4
パワープレイするなら、計算した数を文字列に変換して、さらにreverseかけたものとマッチするかどうか、を総当たりか……。でもそれだとあんまりなので、ちょっと工夫した算数で調整してやったらスマートにいけるかなぁ、と考え中。
Problem.5 ... solved.
手計算で瞬殺。コードに落とすのもめんどくさい。
Problem.6 ... solved.
手計算でいけなくもない。高校レベルの数学。
Problem.7
素数表作ってパワープレイすれば解けるんだろうけど、何かうまい手は無いかとまだ考え中。
Problem.8 ... solved.
よく見れば瞬殺。
Problem.9 ... solved.
これも大学入試レベル。というか昔これ解いたことがある……。というわけで、解法はものの本で読んだから解けたんだけど、それを導出する論理を導き出せていない……。解けたけど情けないことにまだ考え中。
Problem.10
素数表総当たり一択なのかもしれないけど、それもスマートじゃないよなぁ、と考え中。まあでも素数の関わる問題なのでパワープレイに見えてもそれが正解かもしれない。
Problem.11
行列の操作になると思うので、Listを基本とするSchemeだとめんどくさい。ひょっとしたGaucheのライブラリに便利な手続きかデータ構造があるかもしれない。（普通の手続き型言語で）配列使えば瞬殺だと思う。
Problem.12 ... solved.
最初なかなか解けなくて苦労した。素数表作って総当たりで割っていけばパワープレイなんだけど、素数の性質を利用するとだいぶスマートに解ける。やっぱ素数の研究って大事なんだね、ということがよくわかった。
Problem.13 ... solved.
まともに全部足すとあきらかに効率が悪い。ちょっと考えればわりとスマートにいける。
Problem.14 ... solved.
コラッツの数列というのを初めて知ったけど、これ法則性があるようで無いね。
逆関数を作って逆からたどった数列作ってみたり、だいぶあれこれ試行錯誤したけど、そんなこと考えずに普通にパワープレイするのが正解だったかもしれない。
一応試行錯誤した成果はあって、ばさっと計算対象を減らすことはできたものの、さてどこまで計算量減らせたものやら……。
Problem.15 ... solved.
問題14で時間くった割には15はすぐに解けた。数学の問題は基本的にまず試行してみるのが定石だけど、これもスマートな方法がすぐ見つかる。
でも中学で習うような内容の数学が、必要な時に出てこないのってかなり悲しい……。
とりあえず現在のところこんな感じ。まずは、目指せレベル１！ とことで。