6/26に行われたAtCoder Beginner Contest 207の問題の復習です。
Rubyで回答しています。
A Repression (https://atcoder.jp/contests/abc207/tasks/abc207_a)
机の上に、正整数が書かれた3枚のカードがあります。3枚のカードにはそれぞれ整数A,B,Cが書き込まれています。
いま、この中からちょうど2枚のカードを選んで手に持ちました。
手に持ったカードに書き込まれた整数の和として考えられる最大値を求めてください。
入力
A B C
出力
答え
解答
(A,B),(B,C),(A,C)の組み合わせの和を比較して一番大きい数字を出力するという処理を書きました。
A,B,C = gets.split.map(&:to_i)
ab = A + B
bc = B + C
ac = A + C
if ab >= bc && ab >= ac
puts ab
elsif bc >= ab && bc >= ac
puts bc
else
puts ac
end
書きながらもっと上手く短縮して書ける方法あるよなーと思っていたのでもっと短くわかりやすいコードも調べてみました。
入力した値を配列にいれる(①)
入力された値から2つを選び組み合わせる(②-1 combination)
組み合わせた各値を足し合わせる(②-2 .map以下の記述)
②で各組み合わせの和がarrayに格納されたのでこの値の中から最大値を出力する(③)
②-1の段階ではarray = [ [A,B], [B,C],[A,C] ]といった形でarrayに格納されます。
②-2で組み合わせの各値をa,bとして足し合わせる処理がされています。
array = gets.split.map(&:to_i) ・・・①
array = array.combination(2).map{|a,b| a + b} ・・・②
puts array.max ・・・③
おまけ Enumeratorクラスについて
combinationやmapはブロックを与えないとEnumeratorオブジェクトを返します。
Enumeratorって?
Enumeratorクラスはイテレータとして使えると説明がありました。
イテレータとは集合データの各要素に対する繰り返し処理の抽象化という説明がありました。
何がなんやらって感じでしたが、簡単に言うと、Enumeratorのままでは値として返すことができず、putsメソッドなどで値として出力する場合は何かしらのクラスにして返さないと上手く出力できないという感じだと思います。
例えば
puts array.combination(2)
としてもcombinationに対してブロックを与えていないので、値は返ってこず
Enumerator:0x0000
といったような謎の値が出力されます。
きちんと出力したい場合は
puts array.combination(2).to_a
とすれば組み合わせの配列としてArrayクラスに変換されているので配列が結果として返ってきます。
今回の記述ではmapメソッドでブロックを与えているので、最終的なarrayには数値が格納されており、array.maxできちんと出力されたわけですね。
概念が難しく以下のサイトを参考に自分なりに解釈しました。
https://moneyforward.com/engineers_blog/2020/02/04/ruby-enumerator/
B Hydrate (https://atcoder.jp/contests/abc207/tasks/abc207_b)
水色のボールがA個容器に入っています。高橋くんはこの容器に対し、以下の操作を0回以上好きなだけ繰り返します。
水色のボールB個と赤色のボールC個を容器に追加する。
高橋くんの目標は、容器に入っている水色のボールの個数が赤色のボールの個数の D倍以下になるようにすることです。
目標が達成可能かを判定し、可能なら必要な操作回数の最小値を求めてください。
入力
A B C D
出力
目標が達成可能なら操作回数の最小値を出力
達成不可なら-1を出力する
解答
先に達成できない条件を考えたところ2つの条件が必要そうでした。
水色のボールが赤いボールよりも少なくならないといけない、つまり水色よりも赤色のボールのほうが多く容器に追加される必要があります。
なので1つの条件としてB<Cである必要があります。・・・①
2つ目の条件として最初からA個の水色のボールが入っているため、追加されていくC個のボール * Dの値は必ずBより大きくないといつまでたっても目標を達成することができません。
そこで2つ目の条件として B < C*D である必要があります。 ・・・②
①、②を満たさない時が目標を達成できない時なので-1を出力すれば良いと考えました。
A,B,C,Dを標準入力し、①、②を満たさない時-1を出力しreturnで処理を終わらせるように記述しました。
①、②を満たす時は問題文通りもともとあったA個の水色のボールにBを加算し、赤色のボール*Dの値がBを超えるまで繰り返し、その繰り返し回数をcntとして定義しました。
繰り返し処理が終わった後cntを出力すれば答えになります。
A,B,C,D = gets.split.map(&:to_i)
blue = A
red = 0
cnt = 0
if B >= C && B >= (C * D) ・・・①、②の条件を両方満たさない時
puts "-1"
return
end
until blue <= (red * D)
blue += B
red += C
cnt += 1
end
puts cnt
別の解法ではもっと簡単にしていました。
求めたい回数をXとします。
問題文のとおりに水色のボールと赤色のボールを考えると
水色のボールはA+(B*X)
赤色のボールは(C*X)D
となり、これらが以下の式を満たすようなXが存在すればそのXを出力すればOKです。
A+(B*X) <= D(C*X)
式変形すると
A/(C*D-B) <= X
C*D-Bが負となる場合は-1を出力
C*D-Bが正となる場合はA/(C*D-B)を切り上げた数値が求めたい最小値となります。
数値の切り上げ処理はceilメソッドが使えます。
A,B,C,D = gets.split.map(&:to_f)
e = A / (C*D - B)
if e <= 0
puts -1
else
puts e.ceil
end
おまけ IntegerクラスとFloatクラスについて
いつもは数値の入力はto_iでしているのに2つ目の開放ではto_fで入力をしました。
to_iはIntegerクラスとして数値を扱うことを意味し、整数の数字を使う時に使います。
to_fはFloatクラスとして数値を扱うことを意味し、小数点を使った数字の扱いができます。
今回の問題において具体的にを考えてみます。
5 3 2 3 と入力するとします。
to_iで入力した場合にeの値を計算すると
e = 1 となります
これは小数点以下を使わずに整数としてIntegerクラスは数値を扱うためこの結果となります。
to_fで入力した場合だと
e = 1.25となります
これはFloatクラスとして数値を扱うと小数点を使って表現できるためです。
eの値は小数のある値としてもたないとceilメソッドで切り上げ処理ができないためto_fを使って入力を行うことでうまく結果を得ることができたということでした。