# AtCoder Beginner Contest 177

URL: https://atcoder.jp/contests/abc177 (opens new window)

# A

d,t,s = gets.chomp.split(" ").map(&:to_i)
puts s * t >= d ? "Yes" : "No"

# B

s = gets.chomp
t = gets.chomp
min = t.length
(0..s.length-t.length).each do |i|
  count = 0
  t.length.times do |j|
    count += 1 if s[i+j] != t[j]
  end
  min = count if count < min
end
puts min

# C

n = gets.chomp.to_i
# 添字調整
a_arr = [nil] + gets.chomp.split(" ").map(&:to_i)

MOD = 10 ** 9 +7

# A1(A2 + A3 + ... + AN) + A2(A3 + A4 + ... + AN) + ... + AN-2(AN-1 + AN) + AN-1AN
result = 0
sum = 0
n.downto(2) do |i|
  sum += a_arr[i]
  result += a_arr[i-1] * sum
  result %= MOD
end
puts result

# D

Union Findという手法が分からなかった

n,m = gets.chomp.split(" ").map(&:to_i)
ab_arr = m.times.map{gets.chomp.split(" ").map(&:to_i)}

class UnionFind
  attr_accessor :rank, :parent, :union_size
  def initialize(size)
    @rank = Array.new(size, 0)
    @parent = Array.new(size, &:itself)
    @union_size = Array.new(size, 1)
  end
 
  def unite(x, y)
    x_parent = get_parent(x)
    y_parent = get_parent(y)
    return if x_parent == y_parent
 
    if @rank[x_parent] > @rank[y_parent]
      @parent[y_parent] = x_parent
      @union_size[x_parent] += @union_size[y_parent]
    else
      @parent[x_parent] = y_parent
      @union_size[y_parent] += @union_size[x_parent]
      @rank[y_parent] += 1 if @rank[x_parent] == @rank[y_parent]
    end
  end
 
  def get_parent(x)
    @parent[x] == x ? x : (@parent[x] = get_parent(@parent[x]))
  end
end

uf = UnionFind.new(n)
ab_arr.each do |(a, b)|
  uf.unite(a-1, b-1)
end
puts uf.union_size.max
Last Updated: 2020/08/31 15:27