（備忘録）問題解決のための「アルゴリズム数学」〜 6
問題
自分の回答
Rangeの（0...N）の部分を最初（0..N）としていたので最後のN部分（nil)が含まれていることが分からず沼りました。 また書籍見ながらなので回答の出し方はなんとなく分かるのですが、この辺りは今後自分で考えながら出せるようになりたいですね。
N = gets.to_i
h = gets.split.map(&:to_i)
dp = Array.new(N)
(0...N).each do |i|
if i == 0
dp[0] = 0
elsif i == 1
dp[1] = (h[1] - h[0]).abs
else
v1 = dp[i-1] + (h[i] - h[i-1]).abs
v2 = dp[i-2] + (h[i] - h[i-2]).abs
dp[i] = [v1, v2].min
end
end
puts dp[N-1]
（備忘録）問題解決のための「アルゴリズム数学」〜 5
問題
自分の回答
これだと１つ１つのペアをeachするのでTLEになってしまいます。
gets
cnt = 0
gets.split.map(&:to_i).combination(2).each do |i|
if i.inject(:+) == 100000
cnt += 1
end
end
puts cnt
他の回答
gets
# tally要素の数を数え上げた結果をHashで返す
A = gets.split.map(&:to_i).tally
ans = 0
A.each do |key, value|
# 50000を2枚選んだ時だけ異なる
if key == 50000
ans += value * (value - 1) / 2
elsif A[100000 - key]
ans += A[key] * A[100000 - key]
A.delete(100000 - key)
end
end
puts ans
（備忘録）問題解決のための「アルゴリズム数学」〜 4
問題
自分の回答
injectめっちゃ使うようになった
n, r = gets.split.map(&:to_i) puts n.downto((n-r)+1).inject(:*) / (1..r).inject(:*)
その他の回答
combinationという便利メソッドがあるのか
Array#combination (Ruby 3.1 リファレンスマニュアル)
n, m = gets.split.map(&:to_i) puts (1..n).to_a.combination(m).size
（備忘録）問題解決のための「アルゴリズム数学」〜 3
問題
自分の回答
それぞれの色の枚数を数えて、それぞれの色を2枚選ぶ方法を算出して最後に合計を出力している （昨日学習したtallyが役に立つ）
gets h = gets.split.map(&:to_i).tally arr = [] h.each do |k, v| arr << v * ( v - 1 ) / 2 if v >= 2 end puts arr.sum
別解
こっちの方が分かりやすいかも
gets h = gets.split.map(&:to_i).tally sum = 0 h.each do |k, v| sum += v * ( v - 1 ) / 2 end puts sum
（備忘録）問題解決のための「アルゴリズム数学」〜 2
問題
自分の回答
各値段の数をcountし、最後に500円になるパターンを積の法則を利用して算出している。 countを4回やっている部分どうにかしたいけど思い付かなかった
gets price = gets.split.map(&:to_i) a = price.count(100) b = price.count(200) c = price.count(300) d = price.count(400) puts (a * d) + (b * c)
他の方の回答
tallyはself に含まれる要素を数え上げた結果を Hash で返している。（何回か見ている気がする）
Enumerable#tally (Ruby 3.1 リファレンスマニュアル)
ddは全読みをしているらしい
AtCoder に登録したら解くべき精選過去問 10 問を Ruby で解いてみた (しえる版) - Qiita
h=`dd`.split.tally p (h["100"]||0)*(h["400"]||0)+(h["200"]||0)*(h["300"]||0)
（備忘録）問題解決のための「アルゴリズム数学」〜
AtCoderをやって18
問題
自分の回答（不正解）
これだと1回多くカウントされちゃいますね。
n, x = gets.split.map(&:to_i)
a = gets.split.map(&:to_i)
b = 0
cnt = 0
a.each do |i|
if b <= x
b += i
cnt += 1
end
end
puts cnt
他の方回答
N,X = gets.chomp.split(" ").map(&:to_i)
arr = gets.chomp.split(" ").map(&:to_i)
sums = [0]
arr.each do |num|
sums << sums[-1] + num
end
ans = 0
sums.each do |num|
ans += 1 if num <= X
end
puts ans
下のやつは最初はcnt１つ少なくならない？と思ったけど、cnt = 1に設定してればいい訳ですね。自分頭硬いなー
n,x = gets.split.map(&:to_i)
ll = gets.split.map(&:to_i)
sum = 0
cnt = 1
1.upto(n) do |i|
sum += ll[i-1]
if sum <= x
cnt += 1
end
end
puts cnt
