RubyでAtCoder ABC265(A, B, C, D)を解いてみた

はじめに

Webエンジニアを目指して、RubyやRailsをいじってます。
今回は、RubyでAtCoder ABC265のA, B, C, Dを解きました。備忘録として解き方をまとめていきたいと思います。

A - Apple

a-265.rb

x, y, n = gets.split.map(&:to_i)
puts n / 3 * [3 * x, y].min + n % 3 * x

解説

x円払ってりんごを１個手に入れる操作を３回繰り返しりんごを３個手に入れる場合とy円払ってりんご３個を手に入れる場合の小さい方をN/3回分かけ、余ったN%3回分xを足すことで実装することができます。

B - Explore

b-265.rb

n, m, t = gets.split.map(&:to_i)
a = gets.split.map(&:to_i)
hash = m.times.to_h{ gets.split.map(&:to_i) }

(n - 1).times do |i|
  t -= a[i]
  if t <= 0
    puts "No"
    exit
  end
  t += hash[i + 2] if hash[i + 2]
end
puts "Yes"

解説

ボーナス部屋の情報を連想配列hashにもたせます。後は、問題文の通りに実装すればOKです。

C - Belt Conveyor

c-265.rb

# 修正前
h, w = gets.split.map(&:to_i)
arr = Array.new(h){ gets.chomp }

i, j = 0, 0
searched = Array.new(h) { Array.new(w, false) }
loop do
  # searched[[i, j]]でもできますが、実行時間が長くなります
  if searched[i][j]
    puts -1
    break
  end

  searched[i][j] = true
  if arr[i][j] == "U" && i != 0
    i -= 1
  elsif arr[i][j] == "D" && i != h - 1
    i += 1
  elsif arr[i][j] == "L" && j != 0
    j -= 1
  elsif arr[i][j] == "R" && j != w - 1
    j += 1
  else
    puts "#{i + 1} #{j + 1}"
    break
  end
end

c-265.rb

# 修正後
h, w = gets.split.map(&:to_i)
arr = []
h.times do |i|
  str = gets.chomp
  if i == 0
    str = str.tr("U", "S")
  elsif i == h - 1
    str = str.tr("D", "S")
  end

  str[0]  = "S" if str[0]  == "L"
  str[-1] = "S" if str[-1] == "R"
  arr << str
end
arr = arr.join

hash = {}
k = 0
while !hash[k]
  hash[k] = true
  case arr[k]
  when "U"
    k -= w
  when "D"
    k += w
  when "L"
    k -= 1
  when "R"
    k += 1
  when "S"
    puts "#{(k / w) + 1} #{(k % w) + 1}"
    exit
  end
end
puts -1

解説

順にマスを移動していき、通ったマスを連想配列を使って記録します。このとき、すでに通ったマスにもう一度移動した場合は無限にループしてしまうので-1を出力して終了します。

D - Iroha and Haiku (New ABC Edition)

d-265.rb

n, o, q, r = gets.split.map(&:to_i)
a = gets.split.map(&:to_i)

hash = {}
sx = 0
hash[0] = true
a.each do |factor|
    sx += factor
    hash[sx] = true
end

hash.keys.each do |sx|
    sy = sx + o
    if hash[sy] && hash[sy + q] && hash[sy + q + r]
        puts "Yes"
        exit
    end
end
puts "No"

解説

（公式解説を参考にしました）

累積和とSy=Sx+P, Sz=Sy+Q=Sx+P+Q, Sw=Sz+R=Sx+P+Q+Rの関係を利用して、この条件を満たすSy, Sz, SwがあればYesを出力して終了、最後まで条件を満たすものがなければNoを出力します。