最終更新: 2011-03-21T02:43+0900
Problem 31と同じ問題。その解答(20110125p01.03)。ただし、Problem 31には通用した俺の解法では全然終わらない。
Target = 100 a = [1] + [0]*Target (Target-1).downto(1){|pick| 0.upto(Target-pick){|i| a[i+pick] += a[i] } } p a[Target]
素数ごとに一から再試行してるけど計算量はたかがしれてた。
require 'mathn' prime_gen = Prime.new primes = [] prime_gen.each{|prime| primes.push prime a = [1] + [0]*prime primes.each{|pr| 0.upto(prime-pr){|i| a[i+pr] += a[i] } } answer = a.index{|x| 5000 < x } if answer p answer exit end }
まったくひどい解答。76から続くシリーズの締めらしく、何も考えないと計算量が膨大になる。手続き的な解法から一歩進む必要がある。それか一分ルールを無視して何時間もかけて良しとするか。
Target = 100000 a = [1] + [0]*Target (Target-1).downto(1){|pick| 0.upto(Target-pick){|i| a[i+pick] += a[i] } } p a.index{|x| x%1_000_000 == 0}