ABC176のC問題を解いたので、思考プロセスを載せておきます
Contents
問題文
N 人が 1列に並んでおり、前から i 番目の人の身長は Ai です。
https://atcoder.jp/contests/abc176/tasks/abc176_c
それぞれの人の足元に、高さが 0 以上の踏み台を設置し、全ての人が次の条件を満たすようにしたいです。
条件：踏み台を込めて身長を比較したとき、自分より前に、自分より背の高い人が存在しない
この条件を満たす時の、踏み台の高さの合計の最小値を求めてください。
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)