はじめに
Webエンジニアを目指して、RubyやRailsをいじってます。
今回は、RubyでAtCoder ABC258のA, B, C, Dを解きました。備忘録として解き方をまとめていきたいと思います。
A - When?
a-258.rb
# 修正前
k = gets.to_i
k1 = k.to_s
k2 = (k - 60).to_s
puts k < 10 ? "21:0#{k1}" : k < 60 ? "21:#{k1}" : k < 70 ? "22:0#{k2}" : "22:#{k2}"
a-258.rb
# 修正後
k = gets.to_i + 21 * 60
- h, m = k.divmod(60)
- puts "#{h}:" + "%02d" % m
+ puts "%02d:%02d" % k.divmod(60)
B - Number Box
b-258.rb
n = gets.to_i
array = Array.new(n){ gets.chomp.chars }
dx = [-1, -1, -1, 0, 0, 1, 1, 1]
dy = [-1, 0, 1, -1, 1, -1, 0, 1]
max = 0
+ hash = {}
n.times do |i|
n.times do |j|
+ next if hash.keys.max.to_i > array[i][j].to_i
+ hash[array[i][j]] = true
8.times do |k|
count = 0
x, y = i, j
n.times do
count *= 10
count += array[x][y].to_i
x += dx[k]
y += dy[k]
x %= n
y %= n
end
max = [max, count].max
end
end
end
puts max
別解
n = gets.to_i
array = Array.new(n){ gets.chomp.chars.map(&:to_i)}
num_max = array.map(&:max).max
dx = [-1, -1, -1, 0, 0, 1, 1, 1]
dy = [-1, 0, 1, -1, 1, -1, 0, 1]
max = 0
n.times do |i|
n.times do |j|
next if num_max > array[i][j]
8.times do |k|
count = 0
x, y = i, j
n.times do
count *= 10
count += array[x][y].to_i
x += dx[k]
y += dy[k]
x %= n
y %= n
end
max = [max, count].max
end
end
end
puts max
解説
（公式解説を参考にしました）
それぞれの方向に対して場合分けを行い、全探索することで最大値を求めることができます。
C - Rotation
c-258.rb
n, q = gets.split.map(&:to_i)
s = gets.chomp
count = 0
q.times do
t, x = gets.split.map(&:to_i)
case t
when 1
count += x
when 2
puts s[(x - 1 - count) % n]
end
end
解説
countで、操作により末尾の文字を削除して先頭に挿入した回数を記録します。t=1の場合はcountにxを足し、t=2の場合は(x-1-count)%modのインデックスに対応する文字を出力することで実装することができます。
D - Trophy
d-258.rb
n, x = gets.split.map(&:to_i)
array = Array.new(n){ gets.split.map(&:to_i) }
ans = Float::INFINITY
sum = 0
array.each_with_index do |factor, index|
break if index == x
sum += factor.sum
ans = [ans, sum + (x - 1 - index) * factor[1]].min
end
puts ans
解説
（公式解説を参考にしました）
Biが最小になるインデックスをmとすると、m<Mの場合において
B_m < B_M < B_M + A_M
が成り立つため、m(m<=x-1)についてどこで2回以上使えば最小になるかを全探索することにより実装することができます。