AT274の技術だったりなかったり

あっとのTECH LOG

競プロのこととか技術のこととか。たまに日常を書きます。

JOI難易度6 IOI饅頭

問題原文

atcoder.jp

問題要旨

価値がそれぞれ  P_i であるような饅頭が、 M 個と、饅頭を入れるための箱が  N 個ある。
 j 番目の箱は、饅頭を [C_j] 個入れられるが、コストが  E_j かかる。
箱に詰めた饅頭の価値の総和 - 箱のコストを最大化せよ。

  •   1 \leq M \leq 10000
  •   1 \leq M \leq 500

解法

饅頭は明らかに価値の高いものから入れるのが最適。饅頭を  i 個入れられる時の合計価値は累積和をとっておけば高速に求められる。
次に、「饅頭を  i 個入れると決めた時」に、そのための箱を準備する最小コストが欲しくなるが、これはナップサックDPの要領で簡単に求められる。
あとは饅頭を入れる個数全てについて、前計算しておいたものを使って答えを計算していけばいい。
必ずしも箱の要領ぴったりに饅頭を詰める必要はないことに少し注意すること。(価値が1000円の饅頭が1個だけ、 100個入る箱が1円で1個だけ、のような時に困る)

実装

ちょっとTLが怖かったのでDPテーブルは一次元で持っている。
更新は後ろからやる必要がある。ちなみにPyPy3で400ms切ってました(杞憂だった)

import sys
from itertools import accumulate
M, N = map(int, input().split())
Buns = [int(sys.stdin.readline()) for _ in range(M)]
Boxes = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]

# 累積和を取る
M += 1
Buns = [0] + sorted(Buns, reverse=True)
Buns = list(accumulate(Buns))

# dp[i] := i個饅頭を入れるための最小コスト
dp = [float('inf')] * M
dp[0] = 0

for c, e in Boxes:
    for i in reversed(range(M)):
        to = i + c if i + c < M else M - 1
        dp[to] = min(dp[to], dp[i] + e)

ans = 0
for i in range(M):
    ans = max(ans, Buns[i] - dp[i])

print(ans)

感想

ド典型だけど、DPをさくっと倒せると少し誇らしい気持ちになる(えっへん)