「しらみつぶし」がナップサック問題の基本
問題をパッとみて、ナップサック問題に似ていますよね。まず、下記の記事で、ディクショナリーを使ったナップサック問題の解法を確認してください。
この記事では、
今回のケースでは、それぞれの荷物について、「入れる」「入れない」の二択の判断が入ることになります。実際にナップサックに入り切るかどうかは別にして、
・1個目の荷物を入れない場合
・1個目の荷物を入れる場合の結果を記録して、その結果に基づいて、
・2個目の荷物を入れない場合
・2個目の荷物を入れる場合の結果を記録して、その結果に基づいて、
・3個目の荷物を入れない場合
・3個目の荷物を入れる場合・・・ということを N 個目の荷物まで繰り返せば、あらゆる組み合わせパターンを記録することができます。
とあるように、基本的にはすべてのパターンを記録していくという「しらみつぶし」をベースにした解法を紹介しています。
今回の問題についても、同様に考えると、
・1個目の料理をレンジ1に入れる場合（対称性から、1個目についてはレンジ2に入れる場合は考えなくてよい）
の結果を記録して、その結果に基づいて、
・2個目の料理をレンジ1に入れる場合
・2個目の料理をレンジ2に入れる場合
の結果を記録して・・・
という繰り返しになります。それぞれの場合で変化するのは、2個のレンジそれぞれの使用時間合計ですので、これらの組 (t1, t2) が Key になります。で、ナップサック問題であれば、それで実現できる合計価値が Value になりますが、今は、max(t1, t2) が最小になる組を知りたいわけですので、max(t1, t2) を Value にしておきます。そうすると、次の様な非常にシンプルなループが書けます。
dp = {}
dp[(T[1], 0)] = T[1] # dp[(t1, t2)] = max(t1, t2)
for n in range(2, N+1):
dp_n = {}
for t1, t2 in dp.keys():
dp_n[(t1 + T[n], t2)] = max(t1 + T[n], t2)
dp_n[(t1, t2 + T[n])] = max(t1, t2 + T[n])
dp = dp_n
最後に dp[ ] に記録された Value の最小値を選べばOKです。
print(min(list(dp.values())))
で、実は、このシンプルな解法ですべてのケースがパスできます。えっ？！
計算量の考察
上記の解法は、基本、「しらみつぶし」なので、状態 (t1, t2) の数が膨大になって計算量が大変なことになる気がします。単純計算で、 通りの組み合わせですよね。
しかしながら、実際には、t1 のとり得る値は に限定されます。t2 は t1 から一意に決まることに注意すると、状態数は高々
で抑えられるのです。したがって、一般に、全体の計算量は
で収まります。なるほどー。
ちなみに、この問題でも、ナップサック問題と同様に刈り込みを入れることができます。ナップサック問題での刈り込みについては、下記を参照。
具体的には、「max(t1, t2) が大きくなると、min(t1, t2) は小さくなるべき」という条件です。で、dp[ ] への情報の持たせ方をちょっと工夫して、刈り込みをいれてみたのですが、なんと、逆に TLE が発生してしまいます。
刈り込みの際は、Key のソートとスキャンという処理が走るので、こちらのオーバーヘッドが刈り込みによる計算量の削減を上回るということなのでしょう。なるほどー。
