【AtCoder:18回目】AtCoder Beginner Contest 140の振り返り(Ruby)

f:id:ryoutaku_jo:20190907225214p:plain

【目次】

【本題】

振り返り

今回は 9/7(土)に開催されたAtCoder Beginner Contest 140の振り返りを行います。

AtCoder Beginner Contest 140 - AtCoder

今回は3問回答出来ました

f:id:ryoutaku_jo:20190907232429p:plain

レーティング微増

f:id:ryoutaku_jo:20190907232334p:plain

A - Password

A - Password

3桁のパスワードを1〜 Nの数字で構成した場合、何通り存在するかですが、Nの3乗で求めることができます。

以下が提出したコードです。

n = gets.to_i
puts n ** 3

B - Buffet

B - Buffet

番号が+1の料理を食べると満足度が別途加算されるので、その条件も含めて繰り返し処理を行います。

以下が提出したコードです。

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

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

D - Face Produces Unhappiness

まずは、現状で幸福な人の数をカウントします。

次に残りの人の中から、幸福になれる人の最大値を求めます。

K回操作するパターンと、K回より少ない操作で済むパターンの二つで条件を分ける必要があります。

K回より少ない操作で済むパターンでは、幸福になれる人の最大値を求めます。

前提として、全員が同じ方向を向いていたとしても、一人は幸福にはなれません。

その為、幸福になれる余地がある人はn - 1 - countで求められます。これが変化する最大値になります。

K回操作するパターンでは、1回あたりの操作で幸福になれる人の最大値から求めます。

前提として、どのような範囲で反転させたとしても、反転させる範囲の両端にいる人しか幸福の状態は変わりません

その為、1回の反転で幸福になれる人の最大値は2になり、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

《今日の学習進捗(3年以内に10000時間に向けて)》

来週の社内勉強会(課題:デザインパターン)に備えて、勉強を開始中。

学習開始からの期間 :274日
今日までの合計時間:2567h
一日あたりの平均学習時間:9.4h
今日までに到達すべき目標時間:2502h
目標との解離:65h
「10,000時間」まで、

残り・・・「7433時間!」