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

はじめに

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

A - Majority

a-287.rb

n = gets.to_i
array = Array.new(n){ gets.chomp }
puts array.count("For") > n / 2 ? "Yes" : "No"

解説

与えられた文字列で"For"が何回出現したかを調べ、過半数ならYesを、そうでなければNoを出力します。

B - Postal Card

b-287.rb

# 修正前
n, m = gets.split.map(&:to_i)
s_array = Array.new(n){ gets.chomp }
t_array = Array.new(m){ gets.chomp }

ans = 0
n.times do|i|
    m.times do|j|
        if s_array[i][-3..-1] == t_array[j]
            ans += 1
            break
        end
    end
end
puts ans

b-287.rb

# 修正後

n, m = gets.split.map(&:to_i)
s_array = Array.new(n){ gets.chomp }
t_array = Array.new(m){ gets.chomp }

puts s_array.count{ |s| t_array.include?(s[-3..])}

解説

問題文の通りに実装していけば解くことができます。

C - Path Graph?

c-287.rb

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

if m != n - 1
    puts "No"
    exit
end

for i in 1..n
    if array[i].size > 2
        puts "No"
        exit
    end
end

searched = Array.new(n + 1, false)
searched[1] = true
stack = [1]
while node = stack.pop
    array[node].each do|factor|
        if !searched[factor]
            searched[factor] = true
            stack << factor
        end
    end
end

for i in 1..n
    if !searched[i]
        puts "No"
        exit
    end
end
puts "Yes"

解説

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

<方針>
パスグラフとなるには、以下の３つの条件を満たす必要があります。
１）M=N-1である。
２）すべての頂点の次数が2以下である。
３）連結成分が１つである。

<実装方法>
上記の３つの条件を満たすかどうか順に調べていきます。なお、連結成分が１つであるかどうかは、DFSを使って調べています。

D - Match or Not

d-287.rb

s = gets.chomp.chars
t = gets.chomp.chars
lt = t.size

pre = 0
lt.times do|i|
    break if s[i] != "?" && t[i] != "?" && s[i] != t[i]
    pre += 1
end

s = s.reverse
t = t.reverse

suf = 0
lt.times do|i|
    break if s[i] != "?" && t[i] != "?" && s[i] != t[i]
    suf += 1
end

(lt + 1).times do|i|
    if pre >= i && suf >= lt - i
        puts "Yes"
    else
        puts "No"
    end
end

解説

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

preを先頭何文字までが一致させられるか、sufを末尾何文字までが一致させられるかを記憶する変数として更新していきます。最後に、preが先頭i文字より大きく、かつsufが末尾|T|-iよりも大きかったらYesを、そうでなければNoを出力します。

終わりに

C問題とD問題は、より条件やTLEを気にしながら実装していく必要があり難しかったです。