AtCoder Beginner Contest 373 F問題メモ

AtCoder Beginner Contest 373

F - Knapsack with Diminishing Values

問題文

$N$ 種類の品物があり、 $i$ 種類目の品物の重みは $w_i$、価値は $v_i$ です。どの種類の品物も $10^{10}$ 個ずつあります。
品物をいくつか選んで、容量 $W$ のバッグに入れます。
ただし、各品物につき、$k$ 個選ぶと $k^2$ のペナルティが科されます。
- つまり、$i$ 種類目の品物を $k_i$ 個選んだとき、スコアは $k_i v_i - k_i^2$
選んだ品物の重さの総和を $W$ 以下にしつつ、達成できるスコアの総和の最大値 $\displaystyle \sum_{i=1}^{N}k_i v_i - k_i^2$ を求めてください。

制約

$1 \leq N \leq 3000$
$1 \leq W \leq 3000$
$1 \leq w_i \leq W$
$1 \leq v_i \leq 10^9$
入力はすべて整数

解法

以下の素直なナップサックDPを考える。

$\mathrm{DP}[i,j]:=i$ 番目の品物まで考慮し、重さ合計が $j$ の場合の最大スコア

通常のナップサックDP（のうち、同じ品物を何個でも選んで良い版）では、各 $i$ につき、$j$ が小さい方から $\mathrm{DP}[i,j+w_i] \xleftarrow[\max]{} \mathrm{DP}[i-1,j]+v_i$ と更新していくことで $O(W)$、全体 $O(NW)$ で更新できる。

しかし、今回は加算されるスコア $v_i$ が、それまで何個の同じ品物を選んだかによって変化するので上手くいかない。
（そして、その個数別にDPを管理してたら、$O(NW^2)$ となり間に合わない）

以下の性質を利用する。

$\mathrm{DP}[i,j]$ は、もらうDPで考えて、以下の中の最大値である。

$\mathrm{DP}[i-1,j-0w_i] + 0v_i - 0^2$
$\mathrm{DP}[i-1,j-1w_i] + 1v_i - 1^2$
$\mathrm{DP}[i-1,j-2w_i] + 2v_i - 2^2$
$\mathrm{DP}[i-1,j-3w_i] + 3v_i - 3^2$
…

            j-4w j-3w j-2w  j-w   j
DP[i-1]   ....x....x....x....x....x
               ↘   ↘   ↘   ↘  ↓
DP[i]                             *

$\mathrm{DP}[i,j]$ の更新にあたり最大値を取る更新元（$j-k_iw_i$）を $\mathrm{argmax}(j)$ とする。

ここで、以下の事実が成り立つ。

ある $(j_1,j_2)$ の組について、$\mod{w_i}$ が等しく、$j_1 \lt j_2$ ならば、$\mathrm{argmax}(j_1) \le \mathrm{argmax}(j_2)$ である。

略証

背理法で証明する。

$s_1=\mathrm{argmax}(j_1)=j_1-k_1w_i, s_2=\mathrm{argmax}(j_2)=j_2-k_2w_i$ とする。

もし、$j_1 \lt j_2$ の時、$\mathrm{argmax}(j_1) \gt \mathrm{argmax}(j_2)$ となることがあるとする。
その時、以下のようになっている。特に、$u \ge 1, u+k_1 \lt k_2$ である。

|<-u個->|
s2     s1            j1   j2
        |<--- k1個 ---|    |
 |<---------- k2個 --------|

以下の①～④の位置に来る値から関係性を見ると、

|<-u個->|
s2     s1            j1     j2
③     ①<--- k1個 ---|      |
④<----②---- k2個 ----------|

$\mathrm{DP}[i-1,s_1],\mathrm{DP}[i-1,s_2]$ をそれぞれ $d_1,d_2$ で表して、

$\mathrm{DP}[i,j_1]$ の更新に際し ③<① より、$(d_2+(k_1+u)v_i-(k_1+u)^2) \lt (d_1+k_1v_i-k_1^2)$
$\mathrm{DP}[i,j_2]$ の更新に際し ④>② より、$(d_2+k_2v_i-k_2^2) \gt (d_1+(k_2-u)v_i-(k_2-u)^2)$

これを整理すると、$k_2-k_1 \lt u$ となる。しかしこれは $u+k_1 \lt k_2$ と矛盾する。

$\mod{w_i}$ が等しい同士にグループ分けすると、$j$ を増やすに従って $\mathrm{argmax}(j)$ は必ず広義単調増加する。

このような性質を Monotone といい、各 $j$ に対する最大値は Monotone Minima を使うことで $O(W \log{W})$ で求められる。

monotone minima による高速化について | フューチャー技術ブログ

よって、全体で $O(NW \log{W})$ に高速化される。

Python3

n, W = map(int, input().split())
items = [tuple(map(int, input().split())) for _ in range(n)]
dp = [0] * (W + 1)
for w, v in items:
    # print(f'{w=} {v=} {dp=}')
    ndp = [0] * (W + 1)
    for rem in range(w):
        tr = (W - rem) // w + 1
        q = [(0, tr, 0, tr)]
        while q:
            li, ri, lj, rj = q.pop()
            i = (li + ri) // 2
            max_v = -1
            max_j = 0
            t = min(i + 1, rj)
            for j in range(lj, t):
                tmp = dp[j * w + rem] + (i - j) * v - (i - j) ** 2
                if tmp > max_v:
                    max_v = tmp
                    max_j = j
            ndp[i * w + rem] = max_v
            if li < i:
                q.append((li, i, lj, max_j + 1))
            if i + 1 < ri:
                q.append((i + 1, ri, max_j, rj))

    dp = ndp

ans = max(dp)
print(ans)

目次

AtCoder Beginner Contest 373 F問題メモ

F - Knapsack with Diminishing Values

問題文

制約

解法