RubyでAtCoder ABC288(A, B, C)を解いてみた

はじめに

Webエンジニアを目指して、RubyやRailsをいじってます。
今回は、RubyでAtCoder ABC288のA, B, Cを解きました。備忘録として解き方をまとめていきたいと思います。

A - Many A+B Problems

a-288.rb

n = gets.to_i
n.times do
    puts gets.split.map(&:to_i).sum
end

解説

問題文の通りに実装するだけです。

B - Qualification Contest

b-288.rb

n, k = gets.split.map(&:to_i)
array = Array.new(n){ gets.chomp }
puts array[0, k].sort

解説

sortを使って、辞書順にした後の上位K人のハンドルネームを出力すればOKです。

C - Don’t be cycle

c-288.rb

n, m = gets.split.map(&:to_i)

array = Array.new(n + 1){[]}
m.times do
    a, b = gets.split.map(&:to_i)
    array[a] << b
    array[b] << a
end

searched = Array.new(n + 1, false)
count = 0
for i in 1..n
    next if searched[i]
    count += 1
    stack = [i]
    searched[i] = true
    while node = stack.pop
        array[node].each do|i|
            next if searched[i]
            searched[i] = true
            stack << i
        end
    end
end
puts m - (n - count)

解説

<方針と実装方法>
連結成分が閉路とならないためには、(辺の数)=(頂点の数)-1となればいいことがわかります。また、最終的な頂点の数はN個であることがわかっています。以上のことから、最終的な辺の数がN-(連結成分の数)となればすべての連結成分は閉路でないということになります。したがって、答えはM個ある辺をN-(連結成分の数)とするために削除した辺の数(= M-N-(連結成分の数))となります。

なお、連結成分の探索は、292のD問題のときと同様にスタックを使ったDFSで行なっています。

終わりに

今回の問題は、A問題とB問題が比較的簡単で、C問題は考えていて面白かったです。
次回は、AtCoder ABC287を解いていきたいと思います。