はじめに
Webエンジニアを目指して、RubyやRailsをいじってます。
今回は、RubyでAtCoder ABC292のA, B, C, Dを解きました。備忘録として解き方をまとめていきたいと思います。
A - CAPS LOCK
s = gets.chomp
puts s.upcase
解説
upcaseメソッドを使うことで大文字にすることができます。
B - Yellow and Red Card
n, q = gets.split.map(&:to_i)
hash = Hash.new(0)
q.times do
t, x = gets.split.map(&:to_i)
case t
when 1
hash[x] += 1
when 2
hash[x] = 2
when 3
puts hash[x] == 2 ? "Yes" : "No"
end
end
解説
連想配列hashを用意します。そして、イエローカードならその選手（key）に対応するvalueをインクリメントし、レッドカードならそれ以上valueの値が増えることはないので2とします。t=3の場合は、その選手に対応するvalueが2であればYesを出力し、そうでなければNoを出力します。
C - Make Takahashi Happy
n = gets.to_i
hash = Hash.new(0)
for a in 1..n - 1
b = 1
while a * b < n
hash[a * b] += 1
b += 1
end
end
ans = 0
for ab in 1..n - 1
ans += hash[ab] * hash[n - ab]
end
puts ans
解説
（他の方の提出結果を参考にしました）
<方針>
前提として、abが決まればcdはcd=n-abと一意に定まります。また、ab場合の数はa,bの組み合わせによって決まります。これは、cdについても同様です。したがって、1<=ab<=n-1かつ1<=cd<=n-1であることから積が1..n-1となるような正整数の組み合わせの数を求めることで今回の問題は実装することができます。
<実装方法>
まず、連想配列hashに積が1..n-1となるような正整数の組み合わせの数を記録していきます。そして、ansにabとcdそれぞれの場合の数をかけた値を足していき、最後にansを出力します。
D - Unicyclic Components
n, m = gets.split.map(&:to_i)
arr = Array.new(n + 1){[]}
m.times do
u, v = gets.split.map(&:to_i)
arr[u] << v
arr[v] << u
end
searched = Array.new(n + 1, false)
cnt_point = Array.new(n + 1, 0)
cnt_line = Array.new(n + 1, 0)
for i in 1..n
next if searched[i]
searched[i] = true
stack = [i]
cnt_point[i] += 1
while node = stack.pop
arr[node].each do|j|
cnt_line[i] += 1
next if searched[j]
cnt_point[i] += 1
searched[j] = true
stack << j
end
end
end
for i in 1..n
if cnt_line[i] != cnt_point[i] * 2
puts "No"
exit
end
end
puts "Yes"
解説
こういうグラフ系の問題は、DFS(深さ優先探索)やBFS（幅優先探索）といった手法で全探索していきます。個人的には、どちらかが使えればいいと思っています。
<方針>
連結成分ごとに探索して、それぞれにおける頂点の数と辺の数を記録していきます。最後に、それぞれの連結成分における頂点の数と辺の数が一致していればYesを出力し、そうでなければNoを出力します。
<実装方法>
頂点の数を記録するcnt_point配列と辺の数を記録するcnt_line配列を用意します。また、連結成分を再現するためにその頂点と繋がっている頂点から行けるところまでDFSするようにしました。なお、頂点の数については頂点自身およびそこに連結している頂点それぞれについて加算しているため、実際の数の２倍となっています。
終わりに
グラフ系の問題は結構好きですが、今回の問題は工夫が必要で難しかったです。また、C問題についてはRubyはC++などに比べ処理時間が長いため、いかにスマートに書くかが重要であると感じました。