# AtCoder Beginner Contest 170

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

# A

x_arr = gets.chomp.split(" ").map(&:to_i)
puts x_arr.index{|x| x == 0} + 1

# B

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

# 鶴がa匹, 亀がb匹とすると
# a + b == x
# 2 * a + 4 * b == y
# の連立方程式
a = 2 * x - y / 2
b = x - a

if y % 2 == 0 && a >= 0 && b >= 0
  puts "Yes"
else
  puts "No"
end

# C

require "set"
x,n = gets.chomp.split(" ").map(&:to_i)
p_set = Set.new(gets.chomp.split(" ").map(&:to_i))

# xとpの制約から 0 <= ans <= 101
# pの制約から両端(0と101)はp_setの中には含まれない
ans = 0
diff = (x - ans).abs
1.upto(101) do |i|
  next if p_set.include?(i)
  tmp_diff = (x - i).abs
  if tmp_diff < diff
    ans = i
    diff = tmp_diff
  end
end
puts ans

# D

発想としては数列の各要素の倍数を削っていくというもの。

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

hash = {}
# 10 ** 6 と定数でおいても構わない
max = 0
# aごとに個数の数え上げ
a_arr.each do |a|
  hash[a] ||= 0
  hash[a] += 1
  max = a if a > max
end

hash.each do |a, count|
  # 重複がある場合は自身(a)も削除対象
  from_i = count > 1 ? 1 : 2
  to_i = max / a
  # aが1のときにループの回数が一番多い(max回)
  # aがmaxのときにループの回数は一番少ない(1回)
  # max/1 + max/2 + ... + max/max (調和級数:O(log(max)))
  from_i.upto(to_i) do |i|
    # ループ対象を途中で削除しても, 外側のループには影響がない
    hash.delete(a * i)
  end
end

puts hash.size

中のループが調和級数であることがポイント。本番では調和級数とか気にしていなかったけど、なんとなくO(N^2)よりは少なく回りそうだったからそのまま提出したらいけた。

Last Updated: 2020/08/09 18:33