キーエンス プログラミング コンテスト 2020

AtCoder Ruby

https://atcoder.jp/contests/keyence2020
過去問。

A

h, w, n = readlines.map(&:to_i)
puts (n / [h, w].max.to_f).ceil

B

imos法かと思ったが、ちがっていた。

n = gets.to_i
data = n.times.map {gets.split.map(&:to_i)}.map {|x, l| [x - l, x + l]}

result = 0
right_min = -Float::INFINITY

data.sort {|a, b| a[1] <=> b[1]}.each do |arm|
  next if right_min > arm[0]
  result += 1
  right_min = arm[1]
end

puts result

「区間スケジューリング問題」なのだそうである。知らなかった。コードはこれを参考にした。

区間を「終端が早い順」にソートして、とれる順にとる Greedy （貪欲法）で解くことができる

そうである。

C

n, k, s = gets.split.map(&:to_i)

a = Array.new(n)
n.times do |i|
  a[i] = if i < k
    s
  else
    s == 1 ? s + 1 : s - 1
  end
end

puts a.join(" ")

皆んなかしこいなあ。思いつかなかった。K個Sを置いて、あとは残りの部分列でSができないようにすると。