Project Eulerはじました
今日でゴールデンウィークが終わってしまう訳だけれど、僕がこの連休中何をやっていたかというとProjectEulerを解いたり解かなかったりしていた訳で。
ProjectEulerを知らない人も多いだろうから簡単に説明すると、プログラムで数学を解くコンテストみたいなものだ。(僕はサブミットしてないのでよくわからない)問題は英語だけれども和訳したものも乗っているし問題が理解できないなんてことはないと思う。
ここで簡単な例をだそう。
『1000未満で3の倍数または5の倍数のものの総和を求めよ(Problem 1)』
まあ、愚直にやるなら1000回ループをまわして条件を満たしたら足してやればいいだろう。でもこれはあんまりいい手じゃない。O(n)だから十分動くのだけどO(1)にすることができる。その方がスマートだ。ここでは回答については触れないけど、高校数学を見返したら回答がのってる。
まあこんな感じの問題をやっている訳だけれど、競プロっぽくもあり競プロっぽくないとこもある。競プロっぽいなあと思うところは
・再帰的な手法を使う
・オーダーに気をつけないと計算時間が跳ね上がる。
逆に競プロっぽくないと思うのは
・多倍長ばりばりの問題がでる
・入力が定数
・数学的素養?
まあなかなか面白い問題があるからやってみてもらいたい。