はじめに
Ruby学習の一環として「競技プログラミング(競プロ)」に挑戦します。
そのための学習の中で学んだことをアウトプットしていきます。
今回は「AtCoder Beginners Selection」の五問目(Coins)より。
https://atcoder.jp/contests/abs
問題
500円がA枚、100円がB枚、50円がC枚持っています。
これらの硬貨の中から何枚かを選び、合計金額をX円にする方法は何通りあるか。
同じ種類の硬貨同士は区別出来ません。
制約
0 ≤ A,B,C ≤ 50
A + B + C ≥ 1
50 ≤ X ≤ 20,000
A,B,Cは整数である。
Xは50の倍数である。
入力は以下の形で与えられる。
A
B
C
X
# 例
2
2
2
100
出力例
# 上記例の場合
=> 2
条件を満たす選び方は以下の2通り。
500円を0枚、100円を1枚、50円を0枚
500円を0枚、100円を0枚、50円を2枚
解答
まずは僕が最初に書いたコードです。
a = gets.to_i
b = gets.to_i
c = gets.to_i
x = gets.to_i
count = 0
a_array = []
b_array = []
c_array = []
for i in 0..a do
a_array.push(500 * i)
end
for i in 0..b do
b_array.push(100 * i)
end
for i in 0..c do
c_array.push(50 * i)
end
all_array = a_array.product(b_array, c_array)
all_array.each do |one_array|
if one_array.inject(:+) == x
count += 1
end
end
print count
① 硬貨の種類ごとに、0枚からn枚まで、選べる枚数に応じた金額を持つ配列を生成する(for~do~end)。
※100円を3枚持っているなら、[0,2,4,6]の配列が生成されるように。
② 生成された3つの配列から1つずつの要素を取り出し、新たに配列を生成。これを全パターン用意(productメソッド)
③ ②で用意した配列1つ1つに対して、その要素の合計がX(を50で割ったもの)と等しくなるパターンの数を記録する (count)。
上記のような流れで解答しました。
この解答をする中で学んだメソッドを以下にまとめていきます。
for文
for 変数 in オブジェクト do
実行する処理
end
オブジェクトに繰り返す範囲を指定します。
解答では、0から持っている硬貨の枚数まで、0枚、1枚、2枚と順に取り出し、変数に入れるイメージです。
その上でブロック内に指定する処理を繰り返す、といった具合です。
解答では、直前に生成した配列に、枚数に応じた金額を順に入れていっています。
pushメソッド
配列オブジェクト.push(要素, …)
pushメソッドは、配列の末尾に指定した要素を追加します。
productメソッド
#例
[1,2].product([3,4],[5,6])
=> [[1,3,5],[1,3,6],[1,4,5],[1,4,6],[2,3,5],[2,3,6],[2,4,5],[2,4,6]]
複数の配列が持つ全要素の組み合わせを配列にして返します。
eachメソッド
配列オブジェクト.each do |変数|
実行する処理
end
配列から要素をひとつずつ取り出し、変数に代入した上で、
要素の数だけ指定した処理を実行します。
injectメソッド
配列に対して、要素の合計を算出して返します。
今回はシンボル(:+)を用いた記法を使っています。
#例
array = [1, 2, 3]
result = array.inject(:+)
print result
=> 6
改めて調べていて知りましたが、sumメソッドを使うともっと簡単に書けるようです。
#例
array = [1, 2, 3]
result = array.sum
print result
=> 6
短いコードで解答する
ここからは今回の解答を短くしていきます。
縦に並んだ複数の整数入力を受け取る
A, B, C, x = 4.times.map{gets.to_i}
timesメソッド
指定の回数処理を繰り返す場合に使います。
#例
3.times { puts "Hello, World!" }
=>Hello, World!
=>Hello, World!
=>Hello, World!
配列を生成せず、入力された整数を直接判定に使う
解答では配列を生成して、全てのパターンの金額を追加する、ということを行っていましたが、
これによって解答がえらく長いことになってしまっていました。
入力した整数をそのままeach文を使って判定に使用することでコードの長さを抑えられました。
(0..A).each{|a|
(0..B).each{|b|
(0..C).each{|c|
x == (500*a + 100*b + 50*c) ? count +=1 : count += 0
}
}
}
完成
A, B, C, x = 4.times.map{gets.to_i}
count = 0
(0..A).each{|a|
(0..B).each{|b|
(0..C).each{|c|
x == (500*a + 100*b + 50*c) ? count +=1 : count += 0
}
}
}
print count
空白を入れて32行あったコードが9行になりました。
最後に
以上、AtCoder Beginners SelectionでRuby学習【Coins】から学んだメソッド・記法をご紹介しました。
今回のように短いコードで解答する練習は常にやっていきたいです。
他の方の解答を見てみると1行で解答をされている方もいました。
そこまでいくには道のりは長いですが、その分やりがいもありますね!
もし間違いなどございましたら、ご指摘いただけると嬉しいです。