Project Euler (13〜50)
50問目まで解きました。数学を使って工夫すると速く解けたりするようなものについてだけ自分の解答を書きます。
Problem 15
20x20のグリッドの左上から右下までの最短経路数を求めよ
これは2項係数、
の値を計算すれば良いです。2項係数の値はパスカルの三角形の値を上から下へ計算していく方法が効率的です。つまり、以下の漸化式を使います。
コードは次のようになります。
a = [1,1] 2.upto 40 do |n| n.downto 0 do |k| a[k] = (k == 0 || k == n) ? 1 : a[k-1] + a[k] end end puts a[20]
a[k]の計算にa[k-1]を使いますから、内側のループはdowntoです。
Problem 21,23
Problem 21: 10000以下の全ての友愛数の和を求めよ
Problem 23: 2つの過剰数の和で表されない数の和を求めよ
友愛数も過剰数も約数の和を用いて判定します。約数の和はNの因数分解が
の時
で求まるわけなので、Problem 12と同様にして高速に求める事ができます。
例えばProblem 21の場合は以下の様な感じになります。
N = 30000 d = Array.new(N+1,1) exp = Array.new(N+1) 2.upto(N) do |n| if d[n] == 1 then exp.fill(0) n.step(N, n) do |k| exp[k] = exp[k/n] + 1 d[k] *= (1-n**(exp[k]+1))/(1-n) end end end sum = 0 2.upto(10000) do |n| a = d[n]-n b = d[a]-a sum += n if a != b && b == n end puts sum
実行時間は0.36秒程度です。
Problem 26
1/dの循環節の長さが最大となるようなd (< 1000)を求めよ
循環節の長さをkとすると
が整数となるわけなので
が成立するようなkを調べれば良いです。
Problem 27
n^2 + an + b (n=0,1,2,...)が生成する素数列が最長となるようなa,b(|a|<1000,|b|<1000)を求めよ。
n=0で素数である必要があるからbは素数。
n=1で素数である必要があるから1+a+bは素数。従ってaは奇数で、さらに1+a+b > 0。などの必要条件を調べて探索範囲を絞れば良いです。
N = 20000 sieve = [] primes = [] 2.upto(N) do |n| next if sieve[n] primes.unshift(n) if n < 1000 (2*n).step(N,n) {|k| sieve[k] = true} end max_len = 0 max = 0 primes.each do |b| break if b <= max_len (-b+2).step(999,2) do |a| next if sieve[1+a+b] n = 0 while true p = n*n + a*n + b break if p < 0 || (p < N && sieve[p]) raise "N is too small" if p >= N n+=1 end max, max_len = a*b, n if n > max_len end end puts max
実行時間は0.40秒。
Problem 28
下の様にして螺旋状に並べた1001x1001の数字列の、対角にある数の和を求めよ。
21 22 23 24 25 20 7 8 9 10 19 6 1 2 11 18 5 4 3 12 17 16 15 14 13
群数列として考えて、一辺の長さが2*n+1の時の和の一般項を求めると
なのでつまり
にn=500を代入して終わり。
Problem 39
p = a + b + cかつa^2+b^2=c^2
である自然数a,b,cを考える。最も解の数が多くなるpの値を求めよ。
これはProblem 9と同じく2元2次不定方程式の問題なので探索は不要。cを消去して因数分解すると
となるので、まずpは偶数であることが必要。ここでa <= bとすればp-a >= p-bだから
の範囲でp^2/2の約数となるp-aの個数を数えれば良いです。
max = 0 max_p = 0 4.step(1000,2) do |p| count = 0 Math.sqrt(p*p/2).ceil.upto(p) do |k| count += 1 if (p*p/2)%k == 0 end max, max_p = count, p if max < count end puts max_p
実行時間は0.08秒。
Problem 40
0.123456789101112131415161718192021...
のような無限小数の少数第n位をdnとして
d1 * d10 * d100 * d1000 * d10000 * d100000 * d1000000
を求めよ
n桁の数を第n群として群数列的にやればいいです。
r = 1 [1,10,100,1000,10000,100000,1000000].each do |n| k, s = 0, 0 while n > 9*10**k*(k+1) n -= 9*10**k*(k+1) k += 1 end d = (n-1) % (k+1) n = 10**k + (n-1)/(k + 1) r *= (n / 10**(k-d))%10 end puts r
実行時間は0.01秒。
Problem 42,44,45
これらの問題では三角数T(n),五角数P(n),六角数H(n)を扱いますが、これらは以下のようにして値からインデックスを簡単に求める事ができます。これに基づいて解答を作成すれば上手くできます。
Problem 47
連続する4整数で、全てが4つの素因数からなる数であるものを求めよ
「素因数の数」を使いますが、これもProblem 21,23と同様に反復により求められます。
N = 1000000 sieve = Array.new(N+1, 0) 2.upto(N) do |n| if sieve[n] == 0 then n.step(N, n) do |k| sieve[k] += 1 end end if n > 4 && (n-3..n).all? {|k| sieve[k] == 4} puts n-3 exit end end
実行時間は2.75秒。