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

筆者はレート700前後の茶色コーダ

当日解けなかったABC375のE問題を解いていく

実装コード

どうやら部分和の問題に帰着できるようで、
そのとき、入れ替えが増える場合をコストと見立ててテーブルを更新するようだ。

main.py

import sys
from itertools import product
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)

def main():
    N = rI()
    S = 0
    D = []
    for i in range(N):
        Ai, Bi = rLI()
        D.append((Ai,Bi)) 
        S += Bi
    if S % 3 != 0:
        print(-1)
        return
    T = S // 3
    # err(T)
    dp= [[float('inf')]* -~T for _ in range(T+1)]
    dp[0][0] = 0
    for a,b in D:
        ndp= [[float('inf')]* -~T for _ in range(T+1)]
        for i,j in product(range(T+1),repeat=2):
            if a==1:
                if i+b<=T:ndp[i+b][j] = min(ndp[i+b][j],dp[i][j])
                if j+b<=T:ndp[i][j+b] = min(ndp[i][j+b],dp[i][j]+1)
                ndp[i][j] = min(ndp[i][j],dp[i][j]+1)
            if a==2:
                if i+b<=T:ndp[i+b][j] = min(ndp[i+b][j],dp[i][j]+1)
                if j+b<=T:ndp[i][j+b] = min(ndp[i][j+b],dp[i][j])
                ndp[i][j] = min(ndp[i][j],dp[i][j]+1)
            if a==3:
                if i+b<=T:ndp[i+b][j] = min(ndp[i+b][j],dp[i][j]+1)
                if j+b<=T:ndp[i][j+b] = min(ndp[i][j+b],dp[i][j]+1)
                ndp[i][j] = min(ndp[i][j],dp[i][j])
        # if T<=20:
        #     err(a,b)
        #     for ndpi in ndp:err(*[f"{str(n):3s}" for n in ndpi])
        ndp,dp=dp,ndp
    ans = dp[T][T]
    print(ans if ans != float('inf') else -1)
    
if __name__ == '__main__':
    main()

まとめ

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

感想

当日はCやDをギリギリまで時間かけて解いていたので
問題を見ることすらできなかったが、
動的計画法で解ける問題があったとは…😅

解説見ながらでも実装に1時間ぐらいかかったので
結果論としてはDに時間かけたのは間違いではなさそう