# 最近解いたもの

2020/08/31

# AtCoder Beginner Contest 177

# 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

2020/08/29

# AtCoder Beginner Contest 030

URL: https://atcoder.jp/contests/abc030

# C

n,m = gets.chomp.split(" ").map(&:to_i)
x,y = gets.chomp.split(" ").map(&:to_i)
a_arr = gets.chomp.split(" ").map(&:to_i)
b_arr = gets.chomp.split(" ").map(&:to_i)

t = 0
a_i = 0
b_i = 0
result = 0

while true do
  # 次の便を探す
  while !a_arr[a_i].nil? && a_arr[a_i] < t do
    a_i += 1
  end
  break if a_arr[a_i].nil?
  # 往路
  t = a_arr[a_i] + x

  # 次の便を探す
  while !b_arr[b_i].nil? && b_arr[b_i] < t do
    b_i += 1
  end
  break if b_arr[b_i].nil?
  # 復路
  t = b_arr[b_i] + y

  # 往復できたのでインクリメント
  result += 1
end

puts result

2020/08/29

# AtCoder Beginner Contest 035

URL: https://atcoder.jp/contests/abc035

# C

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

# i番目における始点と終点の個数を管理
l_hash = {}
r_hash = {}

q.times do
  l,r = gets.chomp.split(" ").map(&:to_i)
  l_hash[l] ||= 0
  l_hash[l] += 1
  r_hash[r] ||= 0
  r_hash[r] += 1
end

result = []
num = 0
# i番目における白黒を求める
(1..n).each do |i|
  # 始点にかかる個数によって裏返す回数が増える
  num += l_hash[i].to_i
  # 白黒は偶奇によって決まる
  num %= 2
  result << num
  # 終点にかかる個数によって裏返す回数が減る
  num -= r_hash[i].to_i
end

puts result.join("")