ABC383Fを解いた【動的計画法】

筆者はレート800前後の茶～緑コーダ

ABC383当日にACできなかったF問題を解いていく

実装コード

公式解説によると以下のようにDPのテーブルを作ればいいようだ。

dp[c][p]= 色が c 以下の商品から p 円分購入したときの満足度の最大値

テーブルの更新方法とかは公式解説のコードを丸々Pythonに移しただけです

main.py

import sys
from collections import defaultdict
def rI(): return int(sys.stdin.readline().rstrip())
def rLI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def rI1(): return (int(sys.stdin.readline().rstrip())-1)
def rLI1(): return list(map(lambda a:int(a)-1,sys.stdin.readline().rstrip().split()))
def rS(): return sys.stdin.readline().rstrip()
def rLS(): return list(sys.stdin.readline().rstrip().split())
def err(*args): print(*args, file=sys.stderr)

INF = float('inf')

def main():
    N, X, K = rLI()
    P = [0]*N
    U = [0]*N
    C = [0]*N
    ids = defaultdict(list)
    for i in range(N):
        P[i],U[i],C[i] = rLI()
        ids[C[i]-1].append(i)
    # for k in sorted(ids.keys()):
    #     err(k,ids[k])
    dp = [[-INF]*-~X for _ in range(-~N)]
    dp[0][0] = 0
    for i in range(N):
        for idx in ids[i]:
            # err(i,idx,P[idx])
            for j in range(X,P[idx]-1,-1):
                # if N == 3:err(i,j-P[idx],dp[i][j-P[idx]])
                if dp[i][j-P[idx]] != -INF:
                     dp[i + 1][j] = max(dp[i + 1][j], dp[i][j - P[idx]] + U[idx] + K)
                if dp[i + 1][j - P[idx]] != -INF:
                    dp[i + 1][j] = max(dp[i + 1][j], dp[i + 1][j - P[idx]] + U[idx])
        
        for j in range(X+1):
            dp[i + 1][j] = max(dp[i + 1][j], dp[i][j])
            # if N==3:err(i+1,j,dp[i + 1][j])
    print(max(dp[N]))
    
        
if __name__ == '__main__':
    main()

まとめ

ABC383Fを解いた。動的計画法を実装した。

F問題ともなると動的計画法一つでも
テーブルの更新方法が複雑過ぎて理解が難しかった。

この問題を解くには時期尚早な気がしてきたが
とりあえず目を通すだけでも勉強にはなった…ハズ。

いつかADTで出されたときに空でかけるようになりたい。