【AtCoder:19回目】AtCoder Beginner Contest 141の振り返り（Ruby）

【目次】

振り返り
A - Weather Prediction
B - Tap Dance
C - Attack Survival
D - Powerful Discount Tickets

【本題】

振り返り

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

AtCoder Beginner Contest 141 - AtCoder

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

レーティング変化

A - Weather Prediction

問題文高橋君の住む町の天気は、一日ごとに晴れ(Sunny)、くもり(Cloudy)、雨(Rainy)、晴れ、くもり、雨、… と周期的に変化します。

今日の天気を表す文字列 S が与えられるので、明日の天気を予測してください。

制約 S は Sunny, Cloudy, Rainy のいずれかである

私の提出コードは以下の通りです。

s = gets.chomp
 
case s
when 'Sunny'
  puts 'Cloudy'
when 'Cloudy'
  puts 'Rainy'
when 'Rainy'
  puts 'Sunny'
end

以下の様に３通りの出力を配列に格納して、入力によって出し分ける方法だと、よりコードが短縮出来ます。

w=%w(Sunny Cloudy Rainy)
puts w[(w.index(gets.chomp)+1)%3]

B - Tap Dance

問題文高橋君はタップダンスをすることにしました。タップダンスの動きは文字列 S で表され、 S の各文字は L, R, U, D のいずれかです。各文字は足を置く位置を表しており、 1 文字目から順番に踏んでいきます。

S が以下の 2 条件を満たすとき、またその時に限り、 S を「踏みやすい」文字列といいます。

奇数文字目がすべて R, U, D のいずれか。偶数文字目がすべて L, U, D のいずれか。 S が「踏みやすい」文字列なら Yes を、そうでなければ No を出力してください。

制約 S は長さ 1 以上 100 以下の文字列 S の各文字は L, R, U, D のいずれか

条件では４種類の文字のうち３つのいずれかが含まれていると記述されています。

それをそのままコードに落とし込むと記述量が多くなるので、４種類のうち１つを含まないという逆のパターンで考えます。

私の提出コードは以下の通りです。

s = gets.chomp
 
odd = s.chars.select.with_index(1) { |_, i| i.odd? }
even = s.chars.select.with_index(1) { |_, i| i.even? }
 
if odd.include?('L') || even.include?('R')
  puts 'No'
else
  puts 'Yes'
end

C - Attack Survival

問題文高橋君は早押しクイズの大会を開くことにしました。スコアボードの作成を任されたキザハシ君は、次のルールを持つラウンドのポイントを管理するプログラムを書くのに苦戦しています。

このラウンドの参加者は N 人であり、 1 から N までの番号がついています。ラウンド開始時点では全員が K ポイントを持っています。

誰かが問題に正解すると、その人以外の N − 1 人のポイントが 1 減ります。これ以外によるポイントの変動はありません。

ラウンド終了時にポイントが 0 以下の参加者は敗退し、残りの参加者が勝ち抜けます。

このラウンドでは Q 回の正解が出て、 i 番目に正解したのは参加者 A i でした。キザハシ君の代わりに、 N 人の参加者のそれぞれが勝ち抜けたか敗退したかを求めるプログラムを作成してください。

制約入力はすべて整数 2 ≤ N ≤ 10 5 1 ≤ K ≤ 10 9 1 ≤ Q ≤ 10 5 1 ≤ A i ≤ N

( 1 ≤ i ≤ Q )

毎回の個々の点数を更新して行くと処理が非常に重くなります。

そこで、まず各参加者の正答数の合計を集計します。

その正答数と、ラウンド数Qから持ち点Kを引いた値を比較します。

これで勝ち抜けたか敗退したかを判定することが出来ます。

以下が私の提出コードです。

n,k,q = gets.split(' ').map(&:to_i)
ary = []
q.times { ary << gets.to_i }
 
ans = [0] * n
ary.each do |a|
  ans[a-1] += 1
end
 
ans.each do |a|
  if a > q - k 
    puts 'Yes'
  else
    puts 'No'
  end
end

D - Powerful Discount Tickets

問題文高橋くんは N 個の品物を 1 個ずつ順番に買う予定です。

i 番目に買う品物の値段は A i 円です。

高橋くんは M 枚の割引券を持っています。

品物を買う際に割引券を好きな枚数使うことができます。

X 円の品物を買う際に Y 枚の割引券を使った場合、その品物を X 2 Y 円(小数点以下切り捨て)で買うことができます。

最小で何円あれば全ての品物を買うことができるでしょうか。

制約入力は全て整数である。 1 ≤ N , M ≤ 10 5 1 ≤ A i ≤ 10 9

最も金額の大きい商品に割引券を使用するのが、最も割引額が大きくなります。

難点は、割引を繰り返す中で、金額が最大の商品が変動することです。

その為、１回割引をする度に、最大値を探し直す必要があります。

その様に考えて、以下のコードを提出しましたが、TLE（実行時間超過）になってしまいました。

n,m = gets.split.map(&:to_i)
nums = gets.split.map(&:to_i)
 
m.times do |i|
  nums.sort!.reverse!
  nums[0] /= 2
end
 
puts nums.inject(:+)

最大値は別の配列に格納して、そちらで比較を行う方法で通りました。

n,m = gets.split.map(&:to_i)
nums = gets.split.map(&:to_i).sort.reverse

s = [nums.shift / 2] 
(m-1).times do |i|
  if nums == []
    nums = s
    s = [nums.shift / 2]
  elsif nums[0] > s[0]
    s << nums.shift / 2
  else
    s << s.shift / 2
  end
end

nums += s
puts nums.inject(:+)