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()