ABC204 D - Cooking - かんプリンの学習記録

問題概要
解説
おまけ
おまけ2
提出プログラム
感想

問題概要

${N}$ 個の料理があり，それぞれ作るためにオーブンを使う時間は ${T_i}$ である． ${2}$ つのオーブンを用いてすべての料理を作るのにかかる時間は最短何分か．

${1\leq N\leq 100\\ 0\leq T_i\leq 10^3}$

解説

${1}$ つのオーブンのみを用いることを考えると， ${\sum_{i=1}^{N}T_i}$ が答え．

${2}$ つのオーブンだと，料理を ${2}$ つのグループ ${A,B}$ に分けた時の ${\max(\sum_{i\in A}T_i,\sum_{i\in B}T_i)}$ がかかる時間となる．以降どのように料理を ${2}$ つのグループに分けるかが問題となる．

${2^N}$ 通り試していたら時間がかかるので別の方法を考える．

${S}$ を ${T_i}$ の総和( ${\sum_{i=0}^{N}T_i}$ )とおく．
${A}$ を決めると ${B}$ が決まるので ${\max(\sum_{i\in A}T_i,\sum_{i\in B}T_i)=\max(\sum_{i\in A}T_i,S-\sum_{i\in A}T_i)}$ となるから， ${\max(\sum_{i\in A}T_i,S-\sum_{i\in A}T_i)}$ を最小にする ${A}$ はどのようなものかを考える．

ここで， ${\sum_{i\in A}T_i\leq S-\sum_{i\in A}T_i}$ とする( ${\sum_{i\in A}T_i\geq S-\sum_{i\in A}T_i}$ のときは， ${A}$ と ${B}$ を入れ替えることで ${\sum_{i\in A}T_i\leq S-\sum_{i\in A}T_i}$ となる)．このとき，かかる時間は ${S-\sum_{i\in A}T_i}$ であり，これを小さくするには ${\sum_{i\in A}T_i}$ を大きくする必要がある． ${\sum_{i\in A}T_i\leq S-\sum_{i\in A}T_i}$ を変形すると ${\sum_{i\in A}T_i\leq\frac{S}{2}}$ となるので， ${N}$ 個の料理をいくつか選んでできる ${T_i}$ の総和のうち ${\frac{S}{2}}$ 以下の最大値が答えになる．これはナップサック問題とか部分和問題のようにDPで解ける．

ナップサック問題とか部分和問題を知らない人はEDPCとかで練習してください．

おまけ

慣れてないと ${T_i}$ が大きい方から ${\sum T}$ が少ないオーブンに振り分けていくような貪欲が思いつくかもしれませんが，様々な例を考えてみるとWAとなるようなものが見つかってしまいます(4,3,3,2,2など)．このような直感に頼った貪欲は危険なのでやめましょう．面倒かもしれませんが貪欲の正当性の証明をしてください．

おまけ2

途中で最大値の最小化みたいな話が出てきますが，よく「最大値の最小化は二分探索！」と言われているので二分探索を考えてしまうかもしれません．ここで，なぜ最大値の最小化を二分探索により解くことができる問題があるかを説明します．

最大値の最小化は ${min(max(A_1,A_2,\cdots))}$ のような形になり， ${max(A_1,A_2,\cdots)}$ のような部分は扱うのが難しいことがあります．ここで， ${max(A_1,A_2,\cdots)\leq k}$ であることと，任意の ${i}$ に対して ${A_i\leq k}$ であることは同値なので， ${k}$ を決めうつことで ${max(A_1,A_2,\cdots)}$ という ${A_i}$ がたがいに関係し合う式から， ${A_i\leq k}$ という各 ${i}$ について独立に考えることができる式に変換できます．さらに，「 ${i}$ に対して ${A_i\leq k}$ であるか」の真偽は単調であるので二分探索が可能になります．

今回の問題では， ${\min(\max(\sum_{i\in A}T_i,\sum_{i\in B}T_i))}$ です． ${k}$ を決めたとき， ${\sum_{i\in A}T_i\leq k}$ や ${\sum_{i\in B}T_i\leq k}$ は元の問題より簡単に求まるわけではなさそうなので二分探索で解くのは微妙です(解けないことはないが意味ない)．

二分探索で解けるかな？と思うことは悪いことではないですが，このように考えることですぐに無理そうだな(意味ないな)と思うことができます．

例題:https://yukicoder.me/problems/no/710

提出プログラム

pythonのプログラムです．

import numpy as np
 
N = int(input())
T = list(map(int, input().split()))
S = np.sum(T)
DP = np.zeros(S//2+1,dtype=np.bool)
DP[-1] = 1
for i in range(N):
    if S//2+1-T[i] < 0: continue
    DP[:S//2+1-T[i]] |= DP[T[i]:] #numpyを用いていっぺんに遷移
print(S-S//2+np.argmax(DP))

感想

DPを学ぶとき一番最初にみるナップサック問題とか部分和問題に類似する問題でした．ちゃんと勉強しているかどうかが試されました．