ARC027 C - 最高のトッピングにしような

問題原文

atcoder.jp

解法

あるトッピングを交換する時、スペシャルチケットはなるべく温存し、普通のチケットを多く使いたくなる。
すると、最大でもスペシャルチケットの枚数分しかトッピングは手に入らないこと、それさえ守ればスペシャルチケットを普通のチケットと同じように扱えることがわかるので、「どこまで見たか」「何枚使ったか」「いくつ交換したか」で状態を同一視してdpで解ける。

計算量は になる。

実装

PyPyで。MLEしたのでdpテーブル使いまわし。

from copy import deepcopy
import sys
my_input = sys.stdin.readline
 
def main():
    X, Y = map(int, map(int, my_input().split()))
    N = int(input())
    items = [list(map(int, my_input().split())) for i in range(N)]
 
    # dp[i][j][k] := i番目までみてj枚チケットを使い、k個選んでいる時の嬉しさの合計の最大値
    # dp[i + 1] の計算時に dp[i] しか 使わないのでテーブル使いまわし
    dp = [[0] * (X + 1) for _ in range(X + Y + 1)]
    for i, (t, h) in enumerate(items):
        nx_dp = [[0] * (X + 1) for _ in range(X + Y + 1)]
        for j in range(X + Y + 1):
            for k in range(X + 1):
                nx_dp[j][k] = max(nx_dp[j][k], dp[j][k])
                if (k + 1 > X) or (j + t > X + Y):
                    continue
                nx_dp[j + t][k + 1] = max(nx_dp[j + t][k + 1], dp[j][k] + h)
 
        dp = nx_dp
 
    ans = 0
    for j in range(X + Y + 1):
        for k in range(X + 1):
            ans = max(ans, dp[j][k])
    print(ans)
 
 
if __name__ == "__main__":
    main()

感想

numpy使いこなしたい気持ちはあるんですよ。気持ちは。