【AtCoder:18回目】AtCoder Beginner Contest 140の振り返り（Ruby）
【目次】
【本題】
振り返り
今回は 9/7(土)に開催されたAtCoder Beginner Contest 140の振り返りを行います。
AtCoder Beginner Contest 140 - AtCoder
今回は3問回答出来ました
レーティング微増
A - Password
３桁のパスワードを1〜 Nの数字で構成した場合、何通り存在するかですが、Nの３乗で求めることができます。
以下が提出したコードです。
n = gets.to_i
puts n ** 3
B - Buffet
番号が＋１の料理を食べると満足度が別途加算されるので、その条件も含めて繰り返し処理を行います。
以下が提出したコードです。
n = gets.to_i foods = [] 3.times { foods << gets.split(' ').map(&:to_i) } count = 0 n.times do |i| num = foods[0][i] count += foods[1][num-1] if num == foods[0][i-1] + 1 && i > 0 count += foods[2][num-2] end end puts count
C - Maximal Value
Bi ≥ max(Ai, Ai + 1)ということは、Ai = min(Bi - 1, Bi)ということになります。
制約的に全探索でも実装可能です。
以下が提出したコードです。
n = gets.to_i b = gets.split(' ').map(&:to_i) a = [b.first, b.last] 1.upto(n-2) do |i| a << [b[i-1], b[i]].min end p a.inject(:+)
D - Face Produces Unhappiness
まずは、現状で幸福な人の数をカウントします。
次に残りの人の中から、幸福になれる人の最大値を求めます。
K回操作するパターンと、K回より少ない操作で済むパターンの二つで条件を分ける必要があります。
K回より少ない操作で済むパターンでは、幸福になれる人の最大値を求めます。
前提として、全員が同じ方向を向いていたとしても、一人は幸福にはなれません。
その為、幸福になれる余地がある人はn - 1 - countで求められます。これが変化する最大値になります。
K回操作するパターンでは、１回あたりの操作で幸福になれる人の最大値から求めます。
前提として、どのような範囲で反転させたとしても、反転させる範囲の両端にいる人しか幸福の状態は変わりません
その為、１回の反転で幸福になれる人の最大値は２になり、K回だと2 * kとなります。
以上をもとに、実装したコードは以下になります。
n,k = gets.split.map(&:to_i) s = gets.chomp count = 0 (n-1).times do |i| count += 1 if s[i] == s[i+1] end if (n - 1 - count) / 2 >= k count += 2 * k else count += n - 1 - count end puts count
