# AtCoder Beginner Contest 169

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

# A

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

# B

n = gets.chomp.to_i
a_arr = gets.chomp.split(" ").map(&:to_i)
max = 10 ** 18

# 0が1個でもあれば結果は0
# 最初に確認しないと [でかい数, ... , でかい数, 0] の形に対応できない
if a_arr.any?{|a| a == 0}
  puts 0
  exit 
end

result = 1
a_arr.each do |a|
  result *= a
  if result > max
    puts -1
    exit
  end
end

puts result

# C

a,b = gets.chomp.split(" ")
a = a.to_i
# 文字列 -> 整数 (小数で扱うと誤差が生まれるため)
b = b.gsub(".", "").to_i

# bは小数第二位まで与えられていることが確定しているため100で割る
puts (a * b / 100)

# D

require 'prime'

n = gets.chomp.to_i

# 階差数列
# 2 ** 45 > 10 ** 12(= nの最大値)だから45まで用意
# 2 ** 45の2は素数の最小値
arr = [1, 3, 6, 10, 15, 21, 28, 36, 45]

# 素因数分解
# pdは[[p1, p1の指数], [p2, p2の指数], ... ]のような形
pd = n.prime_division

# n = p1^e1 * p2^e2 * ... のようにしたとき
# p1^1), p1^2, ... でnを順番に割っていきたい
result = 0
pd.each do |(p, exp)|
  # 階差数列を利用して exp -> p^iでnを順番に割れる個数に変換
  # ex) exp = 7 なら p^1, p^2, p^3 の3回で割れる. p^4では割れない
  result += arr.index{|a| a > exp}
end

puts result

他の人の回答を見た感じ、階差数列を用いなくても大丈夫っぽい。

pd.each do |(p, exp)|
  i = 1
  cnt = 0
  while exp > 0 do
    exp -= i
    i += 1
    cnt += 1 if exp >= 0
  end
  result += cnt
end

# E

X_iがすべてA_iだったときの中央値が最小、逆にB_iだったときの中央値が最大。中央値として考えられる値は[A_i, B_i]というもの。[A_i, B_i]の値をすべて取れる、という点が腑に落ちなかった。

考え方としては。まずX_iがすべてA_iだったときを考える。そこからどこかのX_iを1ずつ増やす。そうすると中央値は変わらないもしくは1だけ増えることになる。1だけ増えるときってのは、元中央値とX_iの順番が入れ替わるとき。1ずつしか増やしていないから元中央値とX_iの差は1。だから中央値は1だけ増えるということが言える。中央値の推移は連続的になるので[A_i, B_i]の区間がすべて取れる。

この話は配列の長さが奇数のときであって、偶数のときは中央値の増え方は0.5刻みになるのでそこに注意。

n = gets.chomp.to_i

a_arr = []
b_arr = []
n.times do
  a, b = gets.chomp.split(" ")
  a_arr << a.to_i
  b_arr << b.to_i
end

a_arr.sort!
b_arr.sort!

if n % 2 == 0
  median_a = (a_arr[n / 2 - 1] + a_arr[n / 2]).to_f / 2
  median_b = (b_arr[n / 2 - 1] + b_arr[n / 2]).to_f / 2
  puts ((median_b - median_a) * 2 + 1).to_i
else
  median_a = a_arr[(n - 1)/ 2]
  median_b = b_arr[(n - 1)/ 2]
  puts median_b - median_a + 1
end
Last Updated: 2020/08/09 18:33