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

はじめに

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

A - Edge Checker 2

a-285.rb

a, b = gets.split.map(&:to_i)
puts b == a * 2 || b == a * 2 + 1 ? "Yes" : "No"

解説

問題文にある図を見てわかるように、ある数字の点（aとする）とつながる点は2aまたは2a+1となります。

B - Longest Uncommon Prefix

b-285.rb

n = gets.to_i
s = gets.chomp.chars
for i in 1..n - 1
    j = 0
    while j + i < n
        break if s[j] == s[j + i]
        j += 1
    end
    puts j
end

<追記>
コメントで教えていただきました。findメソッドを使って、コンパクトに書くこともできるようです。

別解

n = gets.to_i
s = gets.chomp.chars
for i in 1..n - 1
   puts (0..n - i).find{ |j| s[j] == s[j + i]} || n - i 
end

解説

問題文の通りに実装していけば解くことができます。ただ、与えられた文字列を配列にしないとTLEしてしまうので注意してください。

C - abc285_brutmhyhiizp

c-285.rb

s =gets.chomp
n = s.size
result = (1..n - 1).sum{ |i| 26 ** i }

array = *"A".."Z"
puts result + (0..n - 1).sum{ |i| array.index(s[i]) * (26 ** (n - i - 1))} + 1

<追記>
コメントでいただいた別解になります。

別解

s = gets.chomp.bytes.reverse
puts s.each_with_index.sum { |c, i| (c - 64) * 26 ** i }

解説

（公式解説を参考にしました）

まず、k-1番目以下の文字それぞれについて26^(k-1)通りあるのでresult=(1..n-1).sum{|i|26**i}と初期化します。そして、Aからk番目の文字それぞれについて（arrayをアルファベットの配列としたときに）array.index(s[i]) * (26 ** (n - i - 1)通りあるのでこれらの合計をresultに足せば答えが求まります。

D - Change Usernames

d-285.rb

# 修正前

n = gets.to_i
s_array = []
t_array = []

# 行き先
to = {}

n.times do
    s, t = gets.split(" ")
    s_array << s
    t_array << t
    to[s] = t
end

visited = {}
s_array.each do|s|
    ns = s
    while !visited[ns]
        visited[ns] = true
        break unless to[ns]
        ns = to[ns]
        if ns == s
            puts "No"
            exit
        end
    end
end
puts "Yes"

285.rb

# 修正後

n = gets.to_i
to = n.times.to_h{ gets.split }
# to = Array.new(n){ gets.split }.to_h

visited = {}
to.keys.each do|s|
    ns = s
    while !visited[ns]
        visited[ns] = true
        break unless to[ns]
        ns = to[ns]
        if ns == s
            puts "No"
            exit
        end
    end
end
puts "Yes"

解説

（公式解説を参考にしました）

<方針>
パスグラフになるか、サイクルになるかを調べます。すると、答えは前者ならYes、後者ならNoとなります。

まず、連想配列toに行き先を記録しておきます。また、時間短縮のためにすでに探索したものを記録するための連想配列visitedを用意しておきます。

そして、それぞれのユーザーの現在のユーザー名s[i]に対して、始点をs[i]として行けるところまで更新していきます。このとき、更新していく操作の最中に始点に戻ってしまった場合はサイクルであることを意味するのでNoを出力して終了します。最後まで、探索できればYesを出力します。

終わりに

なかなか解法がパッと思い浮かびませんね...。