ABC204 D Cooking[python]

URL

https://atcoder.jp/contests/abc204/tasks/abc204_d

制約

$$1<= N<= 100$$

$$1 <= T[i]<= 10^{3}$$

問題概要

• N品の料理があり、それぞれT[i]分オーブンを使うことで完成する
• 2つのオーブンがある時、全て完成するまでに最短で何分かかるか？

提出コード

import bisect
n = int(input())
t = list(map(int, input().split()))
# dp[i][j] はi番目まで使った時に2つのオーブンの差がj-10**5になるかどうか
dp = [[False]*(2*10**5+3) for _ in range(n)]
dp[0][t[0]+10**5] = True
dp[0][-t[0]+10**5] = True

for i in range(1, n):
    for j in range(2*10**5+3):
        if dp[i-1][j]:
            dp[i][t[i]+j] = True
            dp[i][-t[i]+j] = True

for i in range(10**5+1):
    if dp[n-1][i+10**5]:
        print((sum(t)+i)//2)
        #print(i, sum(t))
        exit()

考察

• ２つのオーブンがあって、うまく両方のsumが等しくなるようにできるとsum(t)/2になる
• それぞれの料理に対してどっちのオーブンを使うか全探索するとbit全探索で$2^{100}$
• オーブンに入れる順番は関係ない + オーブン毎のsum　の差だけ興味があるので、dpでi番目の料理まで使った時のとりうるsumの差を管理すれば良い
• dp[i]にはとりうる値を全てリストでもつ
• dpの更新は $dp[i] = dp[i-1]+t[i],dp[i-1]-t[i]$ を全てに対して行う
• $NT<=10^{5}$　なので、dp[i]の要素数は$10^{5}$以下で$N<=100$から　$10^{7}$　オーダーで計算できる

実装方針

• dp は正だけの値だけでなく負の値も初期値に入れる
• 要素を単純に追加すると重複してしまうので、既にその値が既出かを判定する必要がある
  • あらかじめ$-10^{5}<=i<=10^{5}$までの配列を持っておいて、flagで管理する方が楽
  • set使っても通るはず。二分探索でもぎり通りそう
• 答えは、最終的にはdp[i]は0を中心に対象になっているはずなので、0以降をみて最も小さいありうる差を見つけてそこから時間を計算する

次回への反省

• dpの定義、更新ができた時点でできたと思ってコードを描き始めたが、その後が思ったより大変だった。
  • 要素が小さい範囲内を動くならflagで管理するのが楽

参考