はじめに
Webエンジニアを目指して、RubyやRailsをいじってます。
今回は、RubyでAtCoder ABC276のA, B, C, Dを解きました。備忘録として解き方をまとめていきたいと思います。
A - Rightmost
a-276.rb
s = gets.chomp.chars
unless s.include?("a")
puts -1
else
puts s.rindex("a") + 1
end
<追記>
コメントでいただいた別解になります。上記コードを簡略したものです。
別解
s = gets.chomp
puts s.rindex("a")&.succ || -1
解説
一番右側にあるaの位置は、rindexメソッドを使って取得することができます。
B - Adjacency List
b-276.rb
n, m = gets.split.map(&:to_i)
array = Array.new(n) { [] }
m.times do
a, b = gets.split.map(&:to_i)
array[a - 1] << b
array[b - 1] << a
end
if array.size == 0
puts 0
exit
end
array.each do |factor|
factor.sort!
puts "#{factor.size} #{factor.join(" ")}"
end
解説
まず、結ばれている都市を配列に格納します。後は、問題文の通りに昇順にソートして出力すればOKです。
C - Previous Permutation
c-276.rb
n = gets.to_i
m = gets.split.map(&:to_i)
i = 0
while m[i + 1..n - 1] != m[i + 1..n - 1].sort
i += 1
end
m[i + 1..n - 1] = m[i + 1..n - 1].sort.reverse
for j in i + 1..n - 1
if m[j] < m[i]
m[i], m[j] = m[j], m[i]
break
end
end
puts m.join(" ")
<追記>
コメントでいただいた別解になります。
別解
def number_in_lex_order(ary)
n = ary.size
return 1 if n <= 1
idx = ary.sort.bsearch_index { _1 >= ary[0] }
(1..n - 1).inject(:*) * idx + number_in_lex_order(ary[1..-1])
end
def nth_sequence_in_lex_order(n, size)
i = 1
table = (1..size - 1).map { i *= _1 }
order = (1..size).to_a
ans = []
n -= 1
size.pred.times do
factorial = table.pop
i = n / factorial
n -= i * factorial
ans << (a = order[i])
order.delete(a)
break if n <= 0
end
ans.concat(order)
end
n = gets.to_i
ps = gets.split.map(&:to_i)
i = number_in_lex_order(ps)
puts nth_sequence_in_lex_order(i - 1, n).join(" ")
解説
（公式解説を参考にしました）
公式解説にあるように先頭に近い要素はなるべく変えず、かつ残った末尾は降順にすることで実装することができます。
D - Divide by 2 or 3
d-276.rb
gets
a = gets.split.map(&:to_i)
g = a.inject(:gcd)
ans = 0
a.each do |factor|
factor /= g
while factor.even?
ans += 1
factor /= 2
end
while factor % 3 == 0
ans += 1
factor /= 3
end
if factor != 1
puts -1
exit
end
end
puts ans
解説
（公式解説を参考にしました）
まず、与えられた配列の要素における最大公約数gを求めます。このとき、nを2でも3でも割り切れない整数とすると、g=2^x * 3^y * nとなります。
そして、各要素をgで割った値に対して2と3それぞれで割り切れるまでansの値をインクリメントしていきます。最後の時点でその要素が1となっていなければ-1を出力して終了、最後まで探索できればansの値を出力します。なお、最初に各要素をgで割っているのは、「各要素が2,3,nのみで構成されていればg,2,3で割っていくことで最後は1となる」ということを利用するためです。