# AtCoder Beginner Contest 180

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

# A

n, a, b = gets.chomp.split(" ").map(&:to_i)
puts n - a + b

# B

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

ans = Array.new(3, 0)
arr.each do |x|
  ans[0] += x.abs
  ans[1] += x ** 2
  ans[2] = x.abs if x.abs > ans[2]
end
ans[1] = Math.sqrt(ans[1])

ans.each do |a|
  puts a
end

# C

n = gets.chomp.to_i

# nの約数を求める
arr = []
(1..Math.sqrt(n)).each do |i|
  if n % i == 0
    arr << i
    j = n / i
    # n = 4, 9, 16, 25, ... のときを考慮
    arr << j if i != j
  end
end

arr.sort.each do |a|
  puts a
end

# D

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

# カコモンジムの強さ増加分: ax - x = x(a - 1)
# Atcoderジムの強さ増加分: b
# 強さが小さいうちはA倍する方が増加分は小さいことに注目

exp = 0
# 倍々する処理は高々O(logX)なので繰り返し処理で大丈夫
while x * (a - 1) < b && x * a < y do
  x *= a
  exp += 1
end

# 和を取る処理は一回で求める
exp += ((y - 1) - x) / b

puts exp

# E

む、むずかしい…

n = gets.chomp.to_i
@arr = n.times.map{ gets.chomp.split(" ").map(&:to_i) }

INF = 10 ** 9
NUM = 1 << n

# 同じ計算を避けるため距離を記憶する
@dist_arr = Array.new(n).map{ Array.new(n, nil) }
def dist(i,j)
  if @dist_arr[i][j].nil?
    a, b, c = @arr[i]
    x, y, z = @arr[j]
    @dist_arr[i][j] = (x - a).abs + (y - b).abs + [0, z - c].max
  end
  @dist_arr[i][j]
end

# dp[bit][i]
# bit: 訪問済み都市
# i: 現在いる都市
dp = Array.new(NUM).map{ Array.new(n, INF) }
# 初期状態
n.times do |i|
  # 都市0 -> 都市i への移動
  dp[1 << i][i] = dist(0, i)
end

NUM.times do |bit|
  # 都市0は必ず通っていること
  next if bit & 1 == 0
  n.times do |i|
    next if dp[bit][i] == INF
    n.times do |j|
      next if i == j
      # 都市i -> 都市j への移動を考える
      cost = dp[bit][i] + dist(i, j)
      bit_j = bit | 1 << j
      dp[bit_j][j] = cost if cost < dp[bit_j][j]
    end
  end
end

# dp[-1][0] = dp[2 ** n - 1][0]
puts dp[-1][0]
Last Updated: 2020/10/18 23:18