ABC204_D – Cooking

問題

D - Cooking

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

atcoder.jp

提出

Submission #44861653 - AtCoder Beginner Contest 194

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

atcoder.jp

3度目で解けた

2度ほど解けず、解説を確認後3度目の挑戦。

2つのオーブンを使って、料理を作る時、N品の料理を全て作るためにかかる時間の最短を求める問題。
各料理にかかる時間は$T_i$分。
もし可能なら、ちょうど半分ずつの時間オーブンを使うのが良いはずなので、最短時間は$(\sum _{i=1}^N{T}_i)/2$分になる。
ちょうど半分が無理なら、$(\sum _{i=1}^N{T}_i)/2$分少し長い時間使うオーブンと、少し短い時間使うオーブンになるはず。
最短時間は$(\sum _{i=1}^N{T}_i)/2$分少し長い時間使うオーブンの時間になる。

以上より、$T_i$の中から任意の数選んだ時、$(\sum _{i=1}^N{T}_i)/2$以上になる、最小の時間を出力すれば良い。
これを求めるためには、dpを使う。
dpを使うと、計算量は$O(N\ast (N\ast \sum _{i=1}^N{T}_i))$になり、大体${10}^7$くらいになるので、間に合う。

このようなタイプのdpはbitsetを使うと実装が楽になる。