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

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

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

実装コード

動的計画法で各栄養素の摂取量を動的計画法で計算しながら、
カロリーX取った場合の最小値最大値を貪欲法で求める。

main.py

from bisect import bisect_left, bisect_right, insort_left, insort_right
from collections import defaultdict, Counter, deque
from functools import reduce, lru_cache
from itertools import product, accumulate, groupby, combinations
import sys
import os
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())
IS_LOCAL = int(os.getenv("ATCODER", "0"))==0
err = (lambda *args, **kwargs: print(*args, **kwargs, file=sys.stderr)) if IS_LOCAL else (lambda *args, **kwargs: None)

def main():
    N, X = rLI()
    
    L = [0]*N
    
    for i in range(N):
        L[i] = rLI()
    
    dp = [[-float('inf') for _ in range(X+1)]for j in range(3)]
    for i in range(3):
        dp[i][0] = 0
    for V,a,c in L:
        v = V-1
        # err(v,a,c)
        for j in range(X,c-1,-1):
            # if X < 100:err(v,i,cur,j,dp[i][cur][j],dp[i][cur][j-c]+a,max(dp[i][cur][j],dp[i][cur][j-c]+a))
            dp[v][j] = max(dp[v][j],dp[v][j-c]+a)
    M = [list(accumulate(dp[i],max)) for i in range(3)]
    s = [0]*3
    # if X < 100:err(cur, [(j,[dp[i][cur][j] for i in range(3)]) for j in range(X+1)])        
    # for j in range(X+1):
    #     if X < 100:err(j,[M[i][j] for i in range(3)])
    for c in range(X):
        m = [M[i][si] for i,si in enumerate(s)]
        mm = min(m)
        mi = m.index(mm)
        # if X < 100:err(c,mi,s,m)
        s[mi] += 1
    print(min([M[i][si] for i,si in enumerate(s)]))

    
if __name__ == '__main__':
    main()

まとめ

動的計画法の設定がうまくいかず、WA、TLEを繰り返した。
式をうまく組み立てられるようになりたい。