【プロジェクトオイラー】数学の難問をプログラムの力で解く！！Part1(オイラープロジェクトの紹介)

　こんにちは。じばるどーねのとぼです。

　皆さん、数学は好きですか？

　プログラミングとかやったりしますか？

わたし、数学とかプログラムで難しい問題を解く行為が（双方全くつよくないしむしろよわいのだけれど。精進しろ）好きで、競技プログラミングとかもちょこちょこやってるんですよ。

　とはいっても今やっているのは日本でとても有名なAtCoderだけなんですが。世界的に有名なCodeforcesやCodeJamなどにも今後挑戦してみたいなと思ってはいます。英語と夜に弱いので、日本時刻で真夜中に行われる英語のコンテストであるCodeforcesなどはきついですが...。

　ここでいう「競技プログラミング」ってのは、プログラミングの問題を制限時間の中でいかに早く、多く解けるかを競う、比較的短時間のコンテストです。AtCoderなどの競技プログラミングでは、各問題にはいくつかのデータセットがあって、各データセットでは入力データが与えられるのでそれに対応した正しい出力データを出したときのみ正解（AC）となります(部分点がある問題もあります)。また、各問題に対して正しい出力を出す場合でも、各問題に与えられた実行時間の制限時間(1秒とか3秒とか)を超えてしまうとTLE（時間制限エラー）となってしまいます。

　一方で、１つの問題に対して１つの解答があり、かつ各問題に実行時間制限がないようなプログラミングの問題を提供するサイトも存在します。その中の１つに、「Project Euler」(プロジェクトオイラー)　というものがあります。かの偉大な数学者オイラーの名を冠している通り、整数問題や幾何問題などの数学の難問をプログラムの力を使って解こう！というものです。

Project Eulerに挑戦してみよう！！

　TLで微妙にこのプロジェクトオイラーが流行っていて、数学とプログラミングが好きな私にはうってつけの内容だったので早速やってみることにしました！！

　では早速、Google先生に[Project Euler]で検索をかけてみましょう。

...。

f:id:tb9810w124816:20180325171613p:plain

＿人人人人人人人＿
＞　全文英語　＜
￣Y^Y^Y^Y^Y^Y^Y^￣

...はい。このように、少しスタートの威圧感が強いですが、まずは登録をしましょう！

f:id:tb9810w124816:20180325172527p:plain

右上の「Register」とかかれたボタンを押して、Username（ニックネーム）やPasswordを決めて登録をしましょう！

　登録が終わったら「Archives」（アーカイブ）と書かれたボタンをクリックすれば早速問題一覧を見ることができます！！

f:id:tb9810w124816:20180325173050p:plain

...こんな感じで問題一覧が表示されています。現在なんと問題数は600を超えています！気長に楽しみましょう。　

　ちなみに各問題の「Difficulty」ってとこにあるオレンジ色のメーターが、その名の通り各問題の難易度の指標になっています。この難易度メーターは5%～100%まであり、メーターが低いほど簡単なものになっています(私は現状40%以上の問題を解けていません...)。見ての通り最初の方の問題は簡単なものが多いので、最初は順番に解いていきましょう。

　まあ実際に、最初の問題を見てみましょう。

f:id:tb9810w124816:20180325173707p:plain

　和訳すると、「1000未満の数で3または5の倍数である数をすべて足すといくつになるか求めなさい」ってことですね。

　(英語でbelow~やunder~は全て～未満となることに注意してください。以下であれば、"5 or under(5以下)"のように"OO or under/below"のような形で表されます。）

　数学の問題として取り組んだらちょっと計算がめんどくさいですが...、プログラムの問題としてはよくある「Fizz Buzz問題」と同程度で、簡単に解けるものですね。

　問題が解けたら、下の回答フォームからAnswerを入力しましょう。

（Confirmation Codeを入力するのを忘れずに！たまに1と7とか見分け付きづらいときがありますが、そういう時は画像をクリックすると新しい画像に更新されます！）

f:id:tb9810w124816:20180325174148p:plain

入力した答えが正解であれば、

f:id:tb9810w124816:20180325182348p:plain

　不正解であれば、

f:id:tb9810w124816:20180325181717p:plain

　といったように、全身白タイツの男が回答の正誤に一喜一憂してくれます。かわいらしいですね。

「英語アレルギーで、問題が解けない！！」

という方も、もしかするといらっしゃるかもしれません。でも大丈夫です。プロジェクトオイラーには有志の方々によって作られた日本語版問題Wikiがあるのです！

　それがこちら↓↓

f:id:tb9810w124816:20180325183436p:plain

　ただし、後半の問題にはまだ翻訳されていないものもあるので、英語ガチ勢の方は是非翻訳完成目指してください（投げ）。

　なお、私は、「むしろ原文で問題解いた方が英語の勉強にもなる！！」と思いながら、２問に１問くらいのペースで和訳をガン見しています(。

だって細かい条件が英語だと理解しにくいんだもん...(甘え)。

　ちなみに、問題に正解すると自分が何番目に正解したかわかるだけでなく、その問題に関する議論を他の正解者とすることができるようになります（議論スレッドに入れるようになる）。このスレッドでは、最初の100個のコメントと最新の100個のコメントが表示されます。自分のソースコードと他の人のソースコードを比較したり評価しあったりするのも成長につながると思います。(なお、議論は英語で())

ちなみに、私のProblem１に用いたソースコード(C++)のメイン関数はこんな感じです↓↓

int main() {
int sum = 0;
  for (int i = 1; i < 1000; i++)
      if (i % 3 == 0 || i % 5 == 0) sum += i;
   cout << sum << endl;
   return 0;
}

　うん。おいしい。

　まあ、何の変哲もない感じですね。Problem1なので、オイラープロジェクトの数ある問題の中でも一番簡単なものになっています。

　もう少し難易度の高い問題(Difficultyはやはり5%だが)を見てみましょう。

f:id:tb9810w124816:20180325190009p:plain

　Problem14。これは、有名な数学の未解決問題の１つ「コラッツ予想」に関する実験をする問題です。数学好きとしては題材がコラッツ予想ってだけでワクワクしますね。

コラッツ予想は、任意の正の整数は

　 ・偶数なら２で割る

　 ・奇数なら３倍して１を足す

という操作を繰り返すと最終的に１になる、というものです。

「ほんとかなぁ」（ゴロリ風に）

と思うわけですが、今までのところ反例となる整数は見つかっていないため正しいのではないかと考えられている命題です。

　で、今回は正の整数を100万未満に限定したとき、１に至るもまでの操作の回数（ステップ）が一番長くなるのはどの整数だろうか、という問題になります。

　いやー、楽しいですね。

　興味のある方は是非自分で実装して解いてみてください。

　数行先でネタバレします（ソースコード載せます）

こんな感じで実装しました。

//EP14.コラッツ問題

int main() {
　　int num[1000001] = { 0 };
　　num[1] = 0, num[2] = 1;
　　int id = 1;
　　for (int i = 3; i < 1000000; ++i) {
　　　if (i % 2 == 0) num[i] = 1 + num[i / 2];
　　　else {
　　　ll t = i;
　　　int s = 0;
　　　while (t >= i) {
　　　　if (t % 2) t = 3 * t + 1;
　　　　else t /= 2;
　　　　s++;
　　　}
　　　num[i] = s + num[t];
　　　}
　　　if (ans < num[i]) {
　　　　ans = num[i];
　　　　id = i;
　　　}
　　}
　　cout << id << endl;
　　return 0;
}