paiza Online Hackathon 解いてみた

天才火消しエンジニア霧島「もしPMおじさんが丸投げを覚えたら」｜paizaオンラインハッカソンLite

以下ネタバレ注意

---

Rubyで解いてみました。早い人で0.02秒とか出てるの、どうやってるんだろう…

pockeさんの採点結果[100点] 完璧ぃぃ！｜paizaオンラインハッカソンLite

こんな感じのコード

@solve = Hash.new
def solve(i, n)
  @solve[i + n * CompNum] ||= (
    last = i + 1 == CompNum
    m = n + Companies[i][0]
    a = m >= ManNum
    c = Companies[i][1]
    if last
      a ? c : 25000000010
    else
      x = a ? c : solve(i + 1, m) + c
      y = solve(i + 1, n)
      x > y ? y : x
    end
  ) 
end

ManNum    = gets.to_i
CompNum   = gets.to_i
Companies = []
CompNum.times do
  Companies << gets.split.map(&:to_i)
end

puts solve(0, 0)

これ以上効率を良くする方法がわからん