Atcoder ABC176 C「Step」 Ruby

  • このエントリーをはてなブックマークに追加

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

問題文

N 人が 1列に並んでおり、前から i 番目の人の身長は Ai です。
それぞれの人の足元に、高さが 0 以上の踏み台を設置し、全ての人が次の条件を満たすようにしたいです。
条件:踏み台を込めて身長を比較したとき、自分より前に、自分より背の高い人が存在しない
この条件を満たす時の、踏み台の高さの合計の最小値を求めてください。

https://atcoder.jp/contests/abc176/tasks/abc176_c

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

n = gets.to_i
a = gets.split.map(&:to_i)

ladder_sum = 0
height = Array.new(n+1)
height[0] = a[0]
1.upto(n) do |i|
  height[i] = chmax(height[i-1], a[i-1])
  ladder_sum += height[i] - a[i-1] if height[i] - a[i-1] >= 0
end
puts ladder_sum

キーポイント

計算量に注意する。一回のループで計算しきる。

思考プロセス

最終的に出力するのは全部の踏み台の高さの合計なので、ladder_sumという変数を用意しました。

また、高さがどんどん大きくなって行くので、現在の取り得る高さをheightという変数で表しました。

n回のループの中で、2つ計算します。

1つ目

i番目の高さです。前の人よりも小さかったらダメ。同じ高さはOKなので、

一個前の大きさ(i-1番目のheight)と現在の人(i番目のa、ただし添え字がずれているのでi-1)で大きい方を採用します。

2つ目

必要だった踏み台の高さを計算します。

上記の1つ目で決定したi番目の高さとi番目の人の高さ(ただし添え字がずれているのでi-1番目)に差があった場合は、それが踏み台の高さです。

踏み台の高さをladder_sumに加えます。

これで一回のループでいけました。O(n)

  • このエントリーをはてなブックマークに追加

SNSでもご購読できます。

スポンサードリンク

コメントを残す

*