PythonでpaizaオンラインハッカソンLiteに挑戦した

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

問題設定

\(n\)個の会社それぞれに、エンジニアの人数\(q\)と価格\(r\)が与えられる
会社をいくつか選んで契約した時に、エンジニアの人数の合計がある値\(m\)以上になるときの最小のコスト(価格の合計)を求める
ただしそれぞれの会社の人数の一部だけを雇うことはできず、会社ごとにまとめて契約することしかできない

解法1 - 動的計画法

どうみてもナップザック問題だ！ということで動的計画法を書いてみたところテストケース7で3.5秒ぐらいかかってしまいました

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

計算量は\(O(mn)\)ぐらい

m = input()
n = input()

qr = [map(int, raw_input().split()) for i in xrange(n)]

MAX = n * 10000 + 20000
MAX2 = n * 10000
dp = [5000000 * 100] * (MAX + 1)

dp[0] = 0

qr.sort(key=lambda x: float(x[1]) / x[0])

result = 5000000 * 100
candidate = set([0])
for i in xrange(n):
    new = set()
    next = dp[:]
    for j in candidate:
        t = dp[j] + qr[i][1]
        k = j + qr[i][0]
        if next[k] > t:
            next[k] = t
        if k >= m and result > t:
            result = t
        if k <= MAX2 and next[k] < result:
            new.add(k)
    candidate |= new
    dp = next
print result

解法2 - 深さ優先探索 + 枝刈り

• paiza オンラインハッカソン lite(https://paiza.jp/poh/kirishima) pythonによるコード #paizahack_lite

Pythonで最速のコードは0.01秒とのことなので、↑のコードを参考にしつつ深さ優先探索と枝狩りのコードを書きました
普通に深さ優先探索すると非常に時間がかかるけど、途中で必要ない探索を打ち切ることで高速に計算できる

こっちの方法は簡単に0.01秒を達成できます

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

枝刈りでどれぐらい計算量が減るのか見積もりが難しいし、最悪の場合はこっちのほうが動的計画法よりも重そうな気がしないでもないですが……

こっちの方法で重要なのは枝刈りに使うためのコストの下限を求めることです
一人あたりの単価が小さい順に会社をソートしておくことで、順番に足していけば必要な人数分のコストの下限が計算できます。
ただし人数が丁度にならない場合があるので、その場合は半端な人数分の価格を足します
たとえば、残り必要な人数が150人の時、100人で価格1000と100人で価格500の会社があるなら、単価の安い価格500の方から100人、価格1000の方から50人分で\(500+1000 \times \frac{50}{100}=1000\)として計算します
端数も含めて効率のよい会社から順にコストを計算しているので、ここで計算した合計のコストは最終的に求めるべきコストと等しいか、それよりも小さくなります(下限)
これにより計算途中で、現在までの最小値とコストの下限を比較して、下限が最小値よりも大きい場合には最小値を下回る可能性がないので探索を打ち切ることができます
コストの下限の計算は下のコードではlower_bound関数で行っています
メモ化もしているので多少速くなっていると思います(何もしないでも0.01秒でしたが

m = input()
n = input()

company = []
for i in xrange(n):
    q, r = map(int, raw_input().split())
    company.append((float(r) / q, q, r))

company.sort()

best = [5000000 * 50]

class memoize(dict):
    def __init__(self, func):
        self.func = func

    def __call__(self, *args):
        return self[args]

    def __missing__(self, key):
        result = self[key] = self.func(*key)
        return result

@memoize
def lower_bound(i, rest):
    unit, num, price = company[i]
    
    cost = price if rest >= num else rest * unit
    rest -= num
    
    if rest <= 0:
        return cost
    elif i + 1 >= n:
        return 100000000
    else:
        return cost + lower_bound(i + 1, rest)

@memoize
def dfs(i, rest, cost):
    rest_new = rest - company[i][1]
    cost_new = cost + company[i][2]
    
    if rest_new <= 0:
        if best[0] > cost_new:
            best[0] = cost_new
    elif i + 1 < n and best[0] >= cost + lower_bound(i + 1, rest_new):
        dfs(i + 1, rest_new, cost_new)
    
    if i + 1 < n and best[0] >= cost + lower_bound(i + 1, rest):
        dfs(i + 1, rest, cost)

dfs(0, m, 0)
print best[0]