Atcoder ABC331: B - Buy One Carton of Milkを整数計画問題・DP・ループ削減で解く方法

• 解法1: 全探索(打ち切りなし)
• 解法2: 全探索(打ち切りとループ削減)
• 解法3: DP
• 解法4: LP

解法1: 全探索(打ち切りなし)

制約を眺めると最大で100個の卵なのでS,M,Lの卵をi,j,k買ったときのケースをすべて探索します。

n, s, m, l = map(int, input().split())
ans = 10**18
for i in range(20):
    for j in range(20):
        for k in range(10):
            if (6*i + 8*j + 12*k) >= n: ans = min(ans, s*i + m*j + k*l)
print(ans)

解法2: 全探索(打ち切りとループ削減)

全探索解から次の点を工夫します。2つ目の工夫は3重ループを2重ループにします。

• N=66だとして Sを10(60個分), Mを1(8個分)買った場合、Mを2以上買うのは明らかに非効率(打ち切る)
• N=70だとしてSを10(60個分), Mを1(8個分)買った場合、Lは1(12個分)以外ありえない。つまり、S,Mが定まるとLは唯一に定まる。

import math
n, s, m, l = map(int, input().split())
ans = 10**18
for i in range(20):
    for j in range(20):
        k = max(0, math.ceil( (n - 6*i - 8*j) / 12)) # kの確定
        ans = min(ans, s*i + m*j + k*l)
        if (6 * i + 8 * j) >= n: break # 打ち切り
print(ans)

解法3: DP

$dp[i]$をi個の卵を買うために必要な最小の価格とします。これをDPで求め、n以上を達成できる価格を調べます。

import math
INF = 10**18
n, s, m, l = map(int, input().split())
dp = [INF] * 120
dp[0] = 0
ans = 10**18
for i in range(0, 100):
    if dp[i] == INF: continue # その個数は達成不可能
    dp[i + 6] = min(dp[i+6], dp[i] + s)
    dp[i + 8] = min(dp[i + 8], dp[i] + m)
    dp[i + 12] = min(dp[i + 12], dp[i] + l)
for i in range(n, 120):
    if dp[i] == INF: continue # その個数は達成不可能
    ans = min(ans, dp[i])
print(ans)

解法4: LP

計画問題であることが自明です。
minimize:
$$
z = s \cdot i + m \cdot j + l \cdot k
$$

subject to:
$$
6s + 8m + 12l \geq n
$$
scipy.linprogには都合が悪いので符号を反転させます。
subject to:

$$
-6s + -8m + -12l \leq -n
$$

これをscipy.linprogします。

from scipy import optimize
n, s, m, l = map(int, input().split())
bds = (0, None) # 0 <= i,j,k
c = [s, m, l]
A = [[-6, -8, -12]]
b = [-n]
res = optimize.linprog(c, A_ub=A, b_ub = b, bounds=(bds,bds,bds), integrality=1)
print(int(res["fun"]))

おまけ

res = optimize.linprog(c, A_ub=A, b_ub = b, bounds=(bds,bds,bds), integrality=1, options={"disp": True} )
するとdetailが見えます。