（備忘録）問題解決のための「アルゴリズム数学」〜 13
問題
自分の回答
規則性があり、2のN乗の一の位は２→４→８→６と繰り返すのでNを４で割った余りが1、2、3、0の時、答えはそれぞれ2、4、8、6となります。
puts case gets.to_i % 4
when 1
2
when 2
4
when 3
8
else
6
end
その他回答
配列使うパターンは思い付かなかった
N = gets.to_i puts [2, 4, 8, 6][(N - 1) % 4]
（備忘録）問題解決のための「アルゴリズム数学」〜 12
問題
自分の回答
規則性を考える問題なので実装はそこまで難しくないです。 （むしろその規則性を見つけ出すのが難しい）
下記の2つの条件を満たせばYesとなります。
条件1 |X| + |Y| <= N
条件2 X + Y の偶奇とNの偶奇が一致
これは書籍に記載があったので理解できましたが、単純に自分で解くのは難しかったでしょう・・・
N, X, Y = gets.chomp.split.map(&:to_i) if (X.abs + Y.abs) <= N && (X + Y) % 2 == N % 2 puts "Yes" else puts "No" end
（備忘録）問題解決のための「アルゴリズム数学」〜 11
問題
回答
rubyに二分探索出来るメソッドが存在したので今回はそちらを使用しました。
Array#bsearch (Ruby 3.1 リファレンスマニュアル)
N, X = gets.split.map(&:to_i)
A = gets.split.map(&:to_i).sort
result = A.bsearch{ |x| x >= X }
puts result == X ? "Yes" : "No"
その他回答
anyってこういう使い方出来るのか・・・
Enumerable#any? (Ruby 3.1 リファレンスマニュアル)
N,X = gets.split puts(gets.split.any?(X)?'Yes':'No')
（備忘録）問題解決のための「アルゴリズム数学」〜 10
問題
回答
これは比較的分かりやすかったですね
N = gets.to_i A = gets.split.map(&:to_i) # i日目に勉強するdp1, i日目に勉強しないdp2の配列を用意する dp1 = Array.new(N+1, 0) dp2 = Array.new(N+1, 0) (0...N).each do |i| dp1[i+1] = dp2[i] + A[i] dp2[i+1] = [dp1[i], dp2[i]].max end puts [dp1[N], dp2[N]].max
（備忘録）問題解決のための「アルゴリズム数学」〜 9
問題
回答コード
これも回答見ながらやりましたが、半分理解できた？くらいの感じですね
# 動的計画法 部分和問題
# 配列初期化の為のメソッドを準備
def darray(n1,n2,ini=nil)
Array.new(n1) { Array.new(n2) { ini } }
end
N, S = gets.split.map(&:to_i)
A = gets.split.map(&:to_i)
# 動的計画法 配列の初期化
dp = darray(N+1, S+1, false)
# 何も選ばずに和が0になる選択肢しかないので、カード0枚目でjが0以外の場合はfalse
dp[0][0] = true
(1..S).each { |s| dp[0][s] = false }
(1..N).each do |i|
(0..S).each do |j|
# 目指す総和より取ろうとするカードの方が大きい場合はカードを取れない
if j < A[i-1]
dp[i][j] = dp[i-1][j]
elsif dp[i-1][j] || dp[i-1][j-A[i-1]]
dp[i][j] = true
else
dp[i][j] = false
end
end
end
puts dp[N][S] ? 'Yes' : 'No'
（備忘録）問題解決のための「アルゴリズム数学」〜 8
問題
自分の回答
書籍に書いてある回答の手引き見て内容理解しててもいざ実装すると難しい。。。 これも他の方の回答見て参考にしています
N,W = gets.split.map(&:to_i)
# 入力を格納する配列
WN = Array.new
N.times do
WN << gets.split.map(&:to_i)
end
# 動的計画法
dp = Array.new
dp[0]=Array.new(W+1,0)
# 商品をeach(最後の分は含まない）
(0...N).each do |i|
dp[i+1] = Array.new
# 重さをeach
(0..W).each do |j|
if j < WN[i][0]
dp[i+1][j] = dp[i][j]
else
dp[i+1][j] = [dp[i][j], dp[i][j-WN[i][0]]+WN[i][1]].max
end
end
end
puts dp[N].max
（備忘録）問題解決のための「アルゴリズム数学」〜 7
問題
自分の回答
書籍に手引きがあるからスムーズに答えられるけど、パッと問題だけ見たらまず分からないなこれ
N = gets.to_i dp = Array.new(N) (0..N).each do |i| i <= 1 ? dp[i] = 1 : dp[i] = dp[i - 1] + dp[i - 2] end puts dp[N]
その他回答
他の回答参考に考えたやつ dp[0]とdp[1]ははそれぞれ1通りしかないので先に初期値入れてその他の値はeachで回せばもう少し分かりやすそう
N = gets.to_i dp = Array.new(2, 1) (2..N).each do |i| dp[i] = dp[i-1] + dp[i-2] end p dp[N]
