# M-SOLUTIONS プロコンオープン 2020

URL: https://atcoder.jp/contests/m-solutions2020

A-Dはそんなに難しくなかったがE, Fは難しすぎて早々に退散。今回Dまで回答できたとしてレーティングのばらつきが結構あったようだ。

# A

本番では愚直にif文を書き連ねたが、200の倍数で級が変わるので計算で求められる

x = gets.chomp.to_i
puts 10 - x / 200

# B

いったん a < b な状態にしてから b < c を目指すというもの

a,b,c = gets.chomp.split(" ").map(&:to_i)
k = gets.chomp.to_i

# a < b < c を目指す
k.times do
  if a >= b
    b *= 2
  elsif b >= c
    c *= 2
  end
end

if a < b && b < c
  puts "Yes"
else
  puts "No"
end

# C

i学期と(i-1)学期の差分に注目すると単なるif文であることに気づける

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

(k..(n-1)).each do |i|
  # i学期の評点: k[i] + k[i-1] + ... + k[i-(k-1)]
  # (i-1)学期の評点: k[i-1] + k[i-2] + ... + k[i-(k-1)] + k[i-k]
  if a_arr[i-k] < a_arr[i]
    puts "Yes"
  else
    puts "No"
  end
end

# D

本番では貪欲法で求めたが動的計画法でも解けるとのこと。なので練習がてら解いてみた。

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

# i日目の最大所持金
dp = [nil, 1000]
(2..n).each do |i|
  # 前日から何もしない場合
  dp[i] = dp[i-1]
  # j日目で買ってi日目で売る場合
  (1..i-1).each do |j|
    # j日目で買う株数
    stock = dp[j] / a_arr[j]
    # j日目の残金 + i日目で得られる金額
    tmp_yen = (dp[j] - stock * a_arr[j]) + (stock * a_arr[i])
    dp[i] = tmp_yen if tmp_yen > dp[i]
  end
end

puts dp[-1]

何がdpで解けるのか解けないのか見極めが難しい...

Last Updated: 2020/07/26 21:19