14-16

Project Euler

Problem 14

「one million以下で、最も長い経過を持つ数字を探せ」
読み違えて「途中で100万以下になったら考えなくて良い」と思ってたら、「スタートした後は100万越えても良い」だった。
100万までのテーブルをC++のnew〜deleteで動的に確保しておき、計算時間を削減。
あとは１から素直に線形で解いた。

Problem 15

「左上から右下まで、20x20のグラフだと何通りあるか？」
プログラム組むより式の方が簡単。

NxNのグラフでp通りあるとして、
  1. N=1:p=2
  2. N=2:p=6
  3. N=3:p=20
  4. N=4:p=70
  5. N=5:p=252

...

となるので、コンビネーションを使って終わり！

Problem 16

「2^1000の、各々の桁を足しあわせた和」
これもズルくbc使って数十桁の数字を取得。
それの各桁を足し合わせて終わり。
n桁目は、n = ( p%(10^n) )/(10^(n-1))とか。