AtCoder 第六回アルゴリズム実技検定 (PAST): N - 活動

「条件を手で計算してみる大切さ」を教えてくれる問題です。ソートしてからナップサックDPで解けます。

問題

$N$ 種類の活動の中から $1$ つ以上を選び、好きな順序で行なう。最初の体力は $H$ であり、活動 $i$ を行うと、得点 $a_i \times \text{(体力)}$ を得た後、体力が $b_i$ 減少する。得られる得点の和の最大値を求めよ。

制約

$1 \le N \le 100$
$1 \le H \le 10^5$
$1 \le a_i, b_i \le 10^5$

考察

活動を行った時に得られる得点が「その時点の体力」に依存するので、そのままナップサックDPは使えません。しかし、活動の順序を全検索（ $100!$ 通り）することは、時間的に不可能です。

ここで、活動 $1$ → 活動 $2$ を行った場合と、活動 $1$ → 活動 $2$ を行った場合の、それぞれ得られる得点を計算してみます。体力の減少は、どちらも同じ $b_1+b_2$ です。

$\displaystyle \begin{aligned} & \left\{ \begin{array}{l} 体力 \, h \\ 得点 \, 0 \end{array} \right. & \xrightarrow{活動1} \, & \left\{ \begin{array}{l} 体力 \, h-b_1 \\ 得点 \, a_1 h \end{array} \right. & \xrightarrow{活動2} \, & \left\{ \begin{array}{l} 体力 \, h-b_1-b_2 \\ 得点 \, a_1 h + a_2(h-b_1) \end{array} \\ \right. \\ & \left\{ \begin{array}{l} 体力 \, h \\ 得点 \, 0 \end{array} \right. & \xrightarrow{活動2} \, & \left\{ \begin{array}{l} 体力 \, h-b_2 \\ 得点 \, a_2 h \end{array} \right. & \xrightarrow{活動1} \, & \left\{ \begin{array}{l} 体力 \, h-b_2-b_1 \\ 得点 \, a_2 h + a_1(h-b_2) \end{array} \\ \right. \end{aligned}$

得られる得点の差は、

$\displaystyle \begin{aligned} \text{score}_{\text{活動1} \rightarrow \text{活動2}} - \text{score}_{\text{活動2} \rightarrow \text{活動1}} &= \left\{a_1 h + a_2(h-b_1) \right\} - \left\{a_2 h + a_1(h-b_2) \right\} \\ &= a_1 b_2 - a_2 b_1 \end{aligned}$

それで、

$\displaystyle \begin{aligned} \text{score}_{\text{活動1} \rightarrow \text{活動2}} \ge \text{score}_{\text{活動2} \rightarrow \text{活動1}} & \Longleftrightarrow a_1 b_2 - a_2 b_1 \ge 0 \\ & \Longleftrightarrow \frac{a_1}{b_1} \ge \frac{a_2}{b_2} \\ \end{aligned}$

となります。ゆえに、 $\displaystyle \frac{a_i}{b_i}$ が大きい方から処理する（降順でソート）のが最善です。

実装例

INF = 10**10
 
N, H = map(int, input().split())
 
Activities = []
for i in range(N):
    a, b = map(int, input().split())
    Activities.append((a, b))
Activities.sort(key=lambda x: (x[0]/x[1]), reverse=True)
 
dp = [[-INF] * (H+1) for _ in range(N+1)]
dp[0][H] = 0

for i in range(N):
    A, B = Activities[i]
    for h in range(H+1):
        dp[i+1][h] = max(dp[i+1][h], dp[i][h]) 
        if h > 0:
            h1 = max(h-B, 0)
            dp[i+1][h1] = max(dp[i+1][h1], dp[i][h] + A*h) 

print(max(dp[N]))

DP高速化

ここからは趣味の範囲です。

このコードで、PyPy で 336 ms でACできますが、さらに高速化できます。

$\text{dp}_{i+1}$ は $\text{dp}_i$ にしか依存しないので、 $\text{dp}_0,\cdots,\text{dp}_N$ を管理するのではなく、 $\text{dp}_i$ （dpとする）と $\text{dp}_{i+1}$ （dp1とする）の2つのみ管理するようにします。ループごとに dp1 を dp で更新し、ループの最後に dp を dp1 に置き換えます。

dp = [-INF] * (H+1)
dp[H] = 0

for A, B in Activities:
    dp1 = [-INF] * (H+1)
    for h in range(H+1):
        dp1[h] = max(dp1[h], dp[h]) 
        if h > 0:
            h1 = max(h-B, 0)
            dp1[h1] = max(dp1[h1], dp[h] + A*h) 
    dp = dp1

print(max(dp))

これで、PyPy で 260 ms です。

さらに、配るDPの更新の時に大きい $h$ のみを更新しているので、 $\text{dp}$ 1本を $h=0,1,\cdots,H$ で更新していけばOKです。

dp = [-INF] * (H+1)
dp[H] = 0

for A, B in Activities:
    for h in range(H+1):
        if h > 0:
            h1 = max(h-B, 0)
            dp[h1] = max(dp[h1], dp[h] + A*h) 

print(max(dp))