ABC166 - Marginalia

A: A?C

puts (gets.chomp == "ABC") ? "ARC" : "ABC"

B: Trick or Treat

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

sunuke = Array.new(n, 0)
k.times do
  gets
  gets.split.each {|a| sunuke[a.to_i - 1] += 1}
end

puts sunuke.count(0)

C: Peaks

できた。うれしい。

n, m = gets.split.map(&:to_i)
heights = [0] + gets.split.map(&:to_i)

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

visited = Array.new(n + 1)
count = 0

dfs = ->(node) {
  return if visited[node]
  visited[node] = true
  highest = graph[node].map {|nxt| heights[nxt]}.max
  count += 1 if !highest || heights[node] > highest
  graph[node].each {|child| dfs.(child)}
}

(1..n).each do |node|
  next if visited[node]
  dfs.(node)
end

puts count

321ms。

しかし、かしこい人たちがいる。

n, m = gets.split.map(&:to_i)
heights = [0] + gets.split.map(&:to_i)

f = Array.new(n + 1, 1)
f[0] = 0

m.times do
  a, b = gets.split.map(&:to_i)
  f[a] = 0 if heights[a] <= heights[b]
  f[b] = 0 if heights[b] <= heights[a]
end

puts f.sum

166ms。何ですか、この簡潔さは。