はじめに
Webエンジニアを目指して、RubyやRailsをいじってます。
今回は、RubyでAtCoder ABC302のA, B, C, Dを解きました。備忘録として解き方をまとめていきたいと思います。
A - Attack
a-302.rb
a, b = gets.split.map(&:to_i)
puts a % b == 0 ? a / b : a / b + 1
B - Find snuke
b-302.rb
h, w = gets.split.map(&:to_i)
array = Array.new(h){ gets.chomp }
directions = [[-1, -1], [-1, 0], [-1, 1], [0, -1], [0, 1], [1, -1], [1, 0], [1, 1]]
str = "nuke"
h.times do |i|
w.times do |j|
next if array[i][j] != "s"
directions.each do |di, dj|
ni = i + di * 4
nj = j + dj * 4
next unless ni >= 0 && ni < h && nj >= 0 && nj < w
flag = true
4.times do |k|
if array[i + di * (k + 1)][j + dj * (k + 1)] != str[k]
flag = false
break
end
end
if flag
5.times do |l|
puts "#{i + 1 + di * l} #{j + 1 + dj * l}"
end
exit
end
end
end
end
解説
（他の方の提出結果を参考にしました）
最初に移動先の設定するための配列directionsを用意しておきます。そして、要素がsであれば、上下左右斜めの8通りで条件を満たす場合があるかを順に調べていくことで実装することができます。
C - Almost Equal
c-302.rb
# 修正前
n, m = gets.split.map(&:to_i)
array = Array.new(n){ gets.chomp }
array.permutation(n) do |na|
flag = true
(n - 1).times do |i|
count = 0
m.times do |j|
count += 1 if na[i][j] != na[i + 1][j]
end
if count != 1
flag = false
break
end
end
if flag
puts "Yes"
exit
end
end
puts "No"
c-302.rb
# 修正後
n, m = gets.split.map(&:to_i)
array = Array.new(n){ gets.chomp.chars }
result = array.permutation(n).any? do |rearranged_array|
rearranged_array.each_cons(2).all?{ |(pre_str, nxt_str)|
pre_str.zip(nxt_str).count{ |c, nc| c != nc } == 1
}
end
puts result ? "Yes" : "No"
解説
Nが８以下と小さいため、並べ替えについて全探索することができます。そして、並べ替え後の文字列について条件を満たすものがあればYesを出力して終了、最後までなければNoを出力します。
D - Impartial Gift
d-302.rb
n, m, d = gets.split.map(&:to_i)
a = gets.split.map(&:to_i).sort
b = gets.split.map(&:to_i)
ans = -1
b.each do |bb|
i = a.bsearch_index{ |aa| aa > bb + d} || n
i -= 1
ans = [ans, a[i] + bb].max if i >= 0 && (a[i] - bb).abs <= d
end
puts ans
解説
（他の方の提出結果を参考にしました）
bsearch_indexメソッドを使って二分探索により差がd以下となる場所を求め、最大値を更新していくことで実装することができます。