AtCoder ARC #075 / ABC #065

arc065-a.rb

x, a, b = gets.chomp.split(" ").map(&:to_i)

if b - a <= 0 then
  puts "delicious"
elsif b - a <= x then
  puts "safe"
else
  puts "dangerous"
end

arc065-b.rb

n = gets.chomp.to_i

a = [0]
n.times do
  a << gets.chomp.to_i
end

curr = 1
ans = 0
n.times do
  ans += 1
  nex = a[curr]
  if nex == 2 then
    puts ans
    exit
  elsif nex == 0 then
    break
  end
  a[curr] = 0
  curr = nex
end
puts -1

arc076-c.rb

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

@k = 10**9 + 7

def fact(n)
  ret = 1
  n.downto(1) do |i|
    ret *= i % @k
    ret %= @k
  end
  return ret
end

if n == m then
  puts 2 * fact(n) ** 2 % @k 
elsif n + 1 == m || n == m + 1 then
  puts fact(n) * fact(m) % @k
else
  puts 0
end

arc076-d.rb

class UnionFind
  def initialize(n)
    @par = (0..n).to_a
    @rank = Array.new(n, 0)
  end
  
  def find(x)
    if @par[x] == x then
      return x
    else
      @par[x] = self.find(@par[x])
      return @par[x]
    end
  end
  
  def unite(x, y)
    x = self.find(x)
    y = self.find(y)
    if x == y then
      return
    end
    if @rank[x] < @rank[y] then
      @par[x] = y
    else
      @par[y] = x
      if @rank[x] == @rank[y] then
        @rank[x] += 1
      end
    end
  end

  def same(x, y)
    return self.find(x) == self.find(y)
  end 
end

class Node
  attr_accessor :x, :y, :i
  def initialize(x, y, i)
    @x = x
    @y = y
    @i = i
  end
end

class Edge
  attr_accessor :u, :v, :cost
  def initialize(u, v, cost)
    @u = u
    @v = v
    @cost = cost
  end
end

def kruscal(edge, n)
  edge.sort_by!{|x| x.cost}
  uf = UnionFind.new(n)
  res = 0
  edge.size.times do |i| 
    e = edge[i]
    if !uf.same(e.u, e.v) then
      uf.unite(e.u, e.v)
      res += e.cost
    end
  end
  return res
end

n = gets.chomp.to_i
edge = []
nodes = []

n.times do |i|
  x, y = gets.chomp.split(" ").map(&:to_i)
  nodes << Node.new(x, y, i)
end

nx = nodes.sort_by{|x| x.x}

(n-1).times do |i|
  n1 = nx[i]
  n2 = nx[i+1]
  edge << Edge.new(n1.i, n2.i, (n1.x - n2.x).abs)
end

ny = nodes.sort_by{|x| x.y}
(n-1).times do |i|
  n1 = ny[i]
  n2 = ny[i+1]
  edge << Edge.new(n1.i, n2.i, (n1.y - n2.y).abs)
end

puts kruscal(edge, n)