paizahack_lite.md

paizaオンラインハッカソン lite をPythonで解いてみた.

結果 は0.01秒.

単純に枝刈りしながら深さ優先探索するだけのコードだけど, あらかじめ単価の安い順にソートしておくのと, Solver.least_cost() あたりの処理とで出来るかぎり浅いところで枝刈りされるようにしている.

とはいえ、このコードで TestCase7が0.01秒というのはちょっと速すぎる気がしないでもない.

# -*- coding:utf-8 -*-
from sys import stdin

class Solver(object):
    """
    最良スコアを計算するためのクラス
    
    target      必要な人員数
    companies   下請会社のリスト(単価が安い順にソートされる)
                個々の要素は (単価, 人数, 費用)のタプル
    best        現時点での最良スコア(費用合計の最小値)
    """
    def __init__(self, target, companies):
        self.target = target
        self.companies = sorted(companies)
        self.best = sum(c for (_, m, c) in companies)

    def solve(self):
        """
        最良スコアを計算する
        """
        self._solve(self.target, 0, 0)
        return self.best

    def _solve(self, target, cost, index):
        """
        最良スコア算出用再帰処理

        target      必要な人員数の残り
        cost        現時点での費用合計
        index       次に検討する下請会社のインデックス
        """
        if target <= 0:
            if cost < self.best:
                self.best = cost
            return
        if len(self.companies) <= index:
            return
        if self.best <= cost + self.least_cost(index, target):
            return

        _, m, c = self.companies[index]
        self._solve(target - m, cost + c, index + 1)
        self._solve(target, cost, index + 1)

    def least_cost(self, index, count):
        """
        index番目以降の下請会社からcount人雇うために最低限かかる費用を返す
        """
        ret = 0
        for i in xrange(index, len(companies)):
            unitcost, member, cost = self.companies[i]
            if member < count:
                ret += cost
                count -= member
            else:
                ret += unitcost * count 
                break
        return ret


target = int(stdin.readline())
companies = []
for i in xrange(int(stdin.readline())):
    member, cost = map(int, stdin.readline().split(' '))
    companies.append((float(cost) / member, member, cost))

s = Solver(target, companies)
print s.solve()

paizahack_lite_ruby.rb

# Ref: https://gist.github.com/wonderful-panda/a019722476a5acfd8c6b
class Solver
  def initialize(target, companies)
    @target = target
    @companies = companies.sort
    @best = companies.map{|x|
      x[0] + x[1] + x[2]
    }.inject(:+)
  end
  def solve
    _solve(@target, 0, 0)
    @best
  end
  def _solve(target, cost, index)
    if target <= 0
      if cost < @best
        @best = cost
      end
      return
    end
    return if @companies.size <= index
    return if @best <= (cost + least_cost(index, target))

    _, m, c = @companies[index]
    _solve(target - m, cost + c, index + 1)
    _solve(target, cost, index + 1)
  end
  def least_cost(index, count)
    ret = 0
    for i in (index..@companies.size-1)
      unicost, member, cost = @companies[i]
      if member < count
        ret += cost
        count -= member
      else
        ret += unicost * count
        break
      end
    end
    ret
  end
end

def input n, res=[]
  n == 0 ? res : (input n-1, res << gets.chomp.split(' ').map(&:to_i))
end

target = gets.chomp.to_i
companies = input(gets.chomp.to_i).map{|x|
  [x.last.to_f / x.first, x.first, x.last]
}
s = Solver.new(target, companies)
puts s.solve