はじめに
Webエンジニアを目指して、RubyやRailsをいじってます。
今回は、RubyでAtCoder ABC286のA, B, C, Dを解きました。備忘録として解き方をまとめていきたいと思います。
A - Range Swap
a-286.rb
N, P, Q, R, S = gets.split.map{ |x| x.to_i - 1}
a = gets.split(" ")
a[P..Q], a[R..S] = a[R..S], a[P..Q]
puts a.join(" ")
解説
問題文の通りに実装すればOKです。
B - Cat
b-286.rb
gets
s = gets.chomp
puts s.gsub(/na/, "nya")
解説
gsubメソッドを使って文字列に含まれるすべての"na"を"nya"に置換しています。
C - Rotate and Palindrome
c-286.rb
n, a, b = gets.split.map(&:to_i)
s = gets.chomp.chars * 2
ans = 10 ** 18
n.times do|i|
sum = a * i
(n / 2).times do|j|
l = i + j
r = i + n - j - 1
sum += b if s[l] != s[r]
end
ans = [ans, sum].min
end
puts ans
別解
n, a, b = gets.split.map(&:to_i)
s = gets.chomp.chars * 2
ans = Float::INFINITY
n.times do|i|
count = (0...n / 2).count{ |j| s[i + j] != s[i + n - j - 1] }
sum = (a * i) + (b * count)
ans = [ans, sum].min
end
puts ans
解説
（公式解説を参考にしました）
まず、A円払って左端の文字を右端に移動するという操作を再現するために与えられた文字列に自身を連結しています。なお、配列にしないとTLEしてしまいます（配列にすればTLEしないということがたまにあります）。また、N回繰り返すと元の文字列に戻るという性質とNが5000以下と小さいことから、A円を支払う操作の回数について全探索することができます。
sumの初期値をA円*（支払った回数）とします。そして、置き換える必要があればB円をsumに加算していき、ansをsumが最小値であったものに更新していきます。最後に、最終的なansを出力すればOKです。
D - Money in Hand
d-286.rb
# 修正前
n, x = gets.split.map(&:to_i)
a_array, b_array = [], []
n.times do
a, b = gets.split.map(&:to_i)
a_array << a
b_array << b
end
dp = Array.new(n + 1){Array.new(x + 1, false)}
dp[0][0] = true
n.times do|i|
(x + 1).times do|j|
(b_array[i] + 1).times do|k|
dp[i + 1][j] = true if j - a_array[i] * k >= 0 && dp[i][j - a_array[i] * k]
end
end
end
puts dp[n][x] ? "Yes" : "No"
d-286.rb
# 修正後
n, x = gets.split.map(&:to_i)
a_array, b_array = Array.new(n) { gets.split.map(&:to_i) }.transpose
dp = Array.new(n + 1){Array.new(x + 1, false)}
dp[0][0] = true
n.times do|i|
(x + 1).times do|j|
(b_array[i] + 1).times do|k|
dp[i + 1][j] = true if j - a_array[i] * k >= 0 && dp[i][j - a_array[i] * k]
end
end
end
puts dp[n][x] ? "Yes" : "No"
解説
（公式解説を参考にしました）
この問題は、DPを使って解くことができます。dp[i][j]：A[1], A2[2], ..., A[i]硬貨を使ってちょうどj円支払えるならtrue、支払えないならfalseとして考えます。
まず、i=0のときはdp[0][0]=true、それ以外はfalseとします。そして、順にj-kA[i]>=0かつdp[i][j-kA[i]]=trueならdp[i+1][j]=trueと更新していきます。最後に、dp[N][X]=trueならYesを、falseならNoを出力すればOKです。
終わりに
C問題とD問題が解けませんでした...悔しい。