はじめに
Webエンジニアを目指して、RubyやRailsをいじってます。
今回は、RubyでAtCoder ABC293のA, B, Cを解きました。備忘録として解き方をまとめていきたいと思います。
A - Swap Odd and Even
a-293.rb
s = gets.chomp
(s.size / 2).times do|i|
s[2 * i], s[2 * i + 1] = s[2 * i + 1], s[2 * i]
end
puts s
<追記>
コメントでいただいた別解になります。sliceメソッドを使うことで隣り合う要素のswapを実現しています。
別解
s = gets.chomp.each_char
puts s.each_slice(2).map { |a, b| b + a }.join
解説
問題文の通りに2iと2i+1の文字をswapして、swap後の文字列を出力すればOKです。
B - Call the ID Number
b-293.rb
# 修正前
n = gets.to_i
a = gets.split.map(&:to_i)
hash = {}
n.times do|i|
next if hash[i + 1]
hash[a[i]] = true
end
ans = []
for i in 1..n
next if hash[i]
ans << i
end
puts ans.size
puts ans.join(" ")
b-293.rb
# 修正後
n = gets.to_i
a = gets.split.map(&:to_i)
hash = {}
a.each_with_index do|i, j|
hash[i] = true unless hash[j + 1]
end
ans = *(1..n).select{ |i| !hash[i]}
puts ans.size
puts ans.join(" ")
解説
まず、呼ばれた人を連想配列hashに記録します。そして、1からnの番号の人で呼ばれなかった人をans配列にもたせます。最後に呼ばれなかった人数と番号を出力します。
C - Make Takahashi Happy
c-293.rb
# 修正前
h, w = gets.split.map(&:to_i)
a = Array.new(h){ gets.split.map(&:to_i)}
ans = 0
[*(0...h + w - 2)].combination(h - 1) do|arr|
route = Array.new(h + w - 2, 1)
arr.map{ |factor| route[factor] = 0 }
i, j = 0, 0
temp = [a[i][j]]
route.each do|factor|
factor == 0 ? i += 1 : j += 1
temp << a[i][j]
end
ans +=1 if temp.uniq.size == temp.size
end
puts ans
c-293.rb
# 修正後
h, w = gets.split.map(&:to_i)
a = Array.new(h){ gets.split.map(&:to_i)}
ans = 0
[*(0...h + w - 2)].combination(h - 1) do|arr|
route = Array.new(h + w - 2, 1)
arr.each{ |factor| route[factor] = 0 }
i, j = 0, 0
hash = {a[i][j]=>true}
route.each do|factor|
factor == 0 ? i += 1 : j += 1
break if hash[a[i][j]]
hash[a[i][j]] = true
end
ans += 1 if hash.size == h + w - 1
end
puts ans
<追記>
コメントでいただいた別解になります。私はスタックを使って解きましたが、このように再帰を使って解くこともできます。
別解
h, w = gets.split.map(&:to_i)
field = Array.new(h) { gets.split.map(&:to_i) }
count = 0
define_method(:go) do |x, y, visited|
return if x == w || y == h
a = field[y][x]
return if visited.include?(a)
visited += [a]
if x == w - 1 && y == h - 1
count += 1
return
end
go(x + 1, y, visited)
go(x, y + 1, visited)
end
go(0, 0, [])
puts count
解説
（他の方の提出結果を参考にしました）
オフセットで考えて、(0, 0)から(h-1, w-1)に移動するので移動回数はh+w-1となります。ここで、下に移動する回数はh-1回となります。なので、combinationメソッドを使って下に移動する場合はroute配列の要素を0としています。そして、要素がすべて異なればansをインクリメントするようにしています。
メモ
・mapメソッドは新たに配列を生成して、それを返している。
終わりに
今回のC問題は少し難しめの全探索系でした。「より簡素なコードにするにはどうしたらよいのか」を考えながらコードを書くようになり、それを自然に行えるようになればコーディングスピードも上がりそうですね！