paiza Online Hackathon をやってみた

もうとっくに応募は締め切られているけれど、とにかく Ruby でやってみました。
　
結果。

やったね！

コードです。

need = gets.to_i
company = gets.to_i
number, cost = [], []
company.times {|i| number[i], cost[i] = gets.split.map(&:to_i)}

h = {}
company.times do |i|
  h1 = h.dup
  h.each do |n, c|
    num = n + number[i]
    ct  = c + cost[i]
    h1[num] = ct if not h1[num] or h1[num] > ct
  end
  h1[number[i]] = cost[i]
  h = h1
end
puts h.select {|n, c| n >= need}.min {|a, b| a[1] <=> b[1]}.last

典型的な動的計画法かと思ったので、それでコーディングしました。

※追記（2017/10/18）
コードの可読性を上げました。それにともないパフォーマンスが微妙に落ちたようです（結果）。
それから下から 4行目は正しくは

  h1[number[i]] = cost[i] if not h1[number[i]] or h1[number[i]] > cost[i]

であるべきですね（結果）。コードの可読性を上げたので気がつきました。読みやすく書くというのはやはり大切ということですね。