Atcoder ABC095 C「Half and Half」 Ruby

ABC095のC問題を解いたので、思考プロセスを載せておきます

問題文

ファーストフードチェーン「ピザアット」のメニューは「A ピザ」「B ピザ」「AB ピザ」の 33 種類です。A ピザと B ピザは全く異なるピザで、これらをそれぞれ半分に切って組み合わせたものが AB ピザです。A ピザ、B ピザ、AB ピザ 11 枚あたりの値段はそれぞれ AA 円、BB 円、CC 円です。

中橋くんは、今夜のパーティーのために A ピザ XX 枚と B ピザ YY 枚を用意する必要があります。これらのピザを入手する方法は、AA ピザや BB ピザを直接買うか、AB ピザ 22 枚を買って A ピザ 11 枚と B ピザ 11 枚に組み替える以外にはありません。このためには最小で何円が必要でしょうか？なお、ピザの組み替えにより、必要な量を超えたピザが発生しても構いません。

https://atcoder.jp/contests/abc095/tasks/arc096_a

ACしたコード

### SNIPPET
  # n = gets.split.map(&:to_i)
  # array = n.times.map { gets.split.map(&:to_i) }
  # [].all?(&:even?)
  # a = [*1..m].repeated_combination(n).to_a
  # [1,2,3,4,5].select { |num| num.even? }  # => [2, 4]
  # ["a","a","b"].group_by(&:itself).map{|k,v| [k, v.count]}.to_h #=> {"a"=>2, "b"=>1}
  # 切り捨て: .floor(2).to_f ,切り上げ： .ceil(2).to_f,四捨五入: round(2)
  # 3.upto(6) do |i|, 6.downto(3) do |i|
  # 公約数125.gcd(100)、公倍数125.lcm(100)
  # PI = Math::PI
  # 高さ = a * Math.sin(w / 180.0 * Math::PI), 底辺 = a * Math.cos(w / 180.0 * Math::PI)
  # def chmax(a, b) a > b ? a : b end
  INF = Float::INFINITY
  def chmin(a, b) a < b ? a : b end

# 1000 2000 5000 4 3
# 1000 2000 5000 3 4
a,b,c,x,y = gets.split.map(&:to_i)

if x < y
  x,y = y,x
  a,b = b,a
end


min_mix = chmin(a+b,2*c)
min_a = chmin(a, 2*c)
s = min_mix * y + (x-y)*min_a
puts s

キーポイント

まず、Aのピザが4枚、Bのピザが3枚必要ならば、

3枚のピザがそれぞれ単体で買う方が安いかmixで買う方が安いのか出しました。残りの一枚を単体で買う方が安いかmixで買う方が安いか出しました。

思考プロセス

最初は動的計画法で解こうと思いました。

こんな感じな表を作るイメージですね！半分ピザの場合があるので、添字は実際の枚数の２倍の数字にしてます。

Aのピザ単体で追加すれば、dp[i+2][j]を、ミックスで追加すればdp[i+1][j+1]を計算していって、dp[2x][2y]まで到達した時の最小値を調べる的な方針ですね。

ですが、制約にひっかかりそうでした。

1≤X,Y≤10**5

なので、最大40の10乗ループ発生するので、あえなく断念

検討の末、単体かmixのどちらが安いかを考えていく方針に転換しました。

条件分岐がめんどくさいので、yの方が大きかった場合は、問答無用で、yとxの場所を入れ替えるようにしました。