最終更新: 2011-02-01T10:42+0900
sum = 1
1.upto((1001-1)/2){|d|
sum += 2 * ( (2*d+1)**2 + (2*d+1)**2-3*2*d ) # (右上の数＋右下の数)の倍で対角4数の和
}
p sum
9の5乗が6万弱なので6桁までの探索で十分。
t = [0, 1, 2**5, 3**5, 4**5, 5**5, 6**5, 7**5, 8**5, 9**5]
sum = 0
10.upto(999999){|n|
sum += n if n == [n, n/10, n/100, n/1000, n/10000, n/100000].inject(0){|a,x| a+t[x%10] }
}
p sum
キレイに書けたんではないかと。
coins = [200, 100, 50, 20, 10, 5, 2] # ,1
remainder = [200]
coins.each{|coin|
remainder.length.times{|n|
remain = remainder[n]
while coin <= remain
remain -= coin
remainder.push remain
end
}
}
p remainder.size
メモリも CPUも節約できる真にすばらしい回答はこちら >Dreamshire | Project Euler Problem 31 Solution
target = 200
coins = [1,2,5,10,20,50,100,200]
ways = [1]+[0]*target
coins.each{|coin|
coin.upto(target){|i|
ways[i] += ways[i-coin]
}
}
p ways[target]
ways[]のインデックスが残金(200-i㌺)で、値が場合の数、なのかな？
有名な問題で、SICPやら何やらに載ってるらしい。2005年以来封印してきたコンクリートマテマティクスを繙くときが来たのかもしれない。<もったいぶってないで勉強しろ
def factorial(n)
r = 1; n.downto(2){|x| r *= x }; r
end
factorials = [1]
9.times{ factorials.push( factorials.last * factorials.length) }
# 9の階乗が36万ちょっとなので 7桁までで十分
sum = 0
10.upto(9999999){|n|
x = n
m = 0
while 0 < x
m += factorials[x%10]
x /= 10
end
sum += n if n == m
}
p sum
Q9の発展。
best_p = 0
solutions_for_p = 0
3.upto(1000){|p|
solutions = 0
1.upto(p/3){|a|
aa = a*a
p_a = p-a
a.upto(p_a/2){|b|
solutions += 1 if aa + b*b == (p_a-b)*(p_a-b)
}
}
if solutions_for_p < solutions
solutions_for_p = solutions
best_p = p
end
}
p best_p
# 一桁 1-9 9個
# 二桁 10-99 90個
# 三桁 100-999 900個
answer = 1
a = [1, 10, 100, 1000, 10000, 100000, 1000000]
width, count = 1, 9
n, pos = 1, 1
loop{
count.times{
if a.first < pos + width
answer *= n.to_s[a.first-pos,1].to_i
a.shift
if a.empty?
p answer
exit
end
end
n += 1
pos += width
}
width, count = width+1, count*10
}
names = ["A","ABILITY","ABLE",...]
name_values = names.map{|name| (0...(name.length)).inject(0){|wv,i| wv + name[i] - ?A + 1 } }.sort
count = 0
n, tn = 1, 1
until name_values.empty?
name_values.shift while ! name_values.empty? and name_values.first < tn
while ! name_values.empty? and name_values.first == tn
count += 1
name_values.shift
end
n, tn = n+1, tn+n+1
end
p count
わかんね。1^1, 2^2から 250250^250250までを、250で割った余りで 250種類に分類するところまでやったけど、そこから組み合わせの数を妥当な時間で計算できる気がしない。1要素で 250の倍数になるもの、ならないもの、2要素で 250の倍数になるもの、ならないもの、……、249要素で 250の倍数になるもの、を考えていくのかと思ったけど、それらの要素が有限なために自由には組み合わせられない(不可能な組み合わせが生じる)、単純に掛け合わせて可能な場合の数を求められない、というところで行き詰まった。ならばと、Q31で参考にしたスクリプトを下敷きに 250で割った余りをインデックスに、場合の数を値にした配列を使おうかと思ったけど、残金をインデックスにした場合と違って余りは循環する、というあたりで処理が一直線に進まなくてギブアップ。
memo = [[0, 1]]*250 # [exp, mod]
memo2 = (0...250).map{|x| x**250 } # exp=250特化版
set = [0]*250
1.upto(250250).each{|i|
basemod = i%250
mod = (memo[basemod][1] * (i-memo[basemod][0] == 250 ? memo2[basemod] : basemod**(i-memo[basemod][0]))) % 250
memo[basemod] = [i, mod]
set[mod] += 1
}
p set