ABC204 D 解答

D - Cooking（832）

問題

D - Cooking

問題文

高橋君は料理 1 から N の N 品の料理を作ろうとしています。
料理 i はオーブンを連続した Ti 分間使うことで作れます。1 つのオーブンを
2 つ以上の料理のために同時に使うことはできません。
2 つのオーブンを使えるとき、N 品の料理を全て作るまでに最短で何分かかりますか？　なお、オーブンを使う時間以外は無視できるものとします。

制約

1 ≤ N ≤ 100
1 ≤ Ti ≤ 10^3
入力に含まれる値は全て整数である

考察

本問題では2つのオーブンを使って、最も効率よく料理を作ったときの時間を求めます。

オーブンが2つあって最も速く作るためにはそれぞれの料理をどちらに振り分ければいいか？

と考えるのですが、これは少し考えにくいです。ですので、一旦次の値を考えてみることにします。

オーブンは１つしかない
いくつか料理を選択する
その料理を全部作るのにかかる時間

この値です。適当に選んだ料理の調理時間の合計がわかれば、次の式で選んでいない料理時間も求めることができます。

選んでいない料理の調理時間＝
全ての料理の調理時間ー選んだ料理の調理時間

まあ、それはそうだよね、という式です。言ってることは同じですが、これにて、選んだ料理の調理時間さえ求めればよくなりました。

さて、この値を求める方法の一つに全探索がありますね。ある料理に対して調理する、しないの2パターン考えられますので、その組み合わせの総数は2^Nです。今回、n≦100ですので、とんでもない値になります。これはちょっと間に合わなさそうです（鳩ノ巣原理と時間の制約を使うと実はこれでも解くことが可能です）。

今回はこちらをdp（動的計画法）を用いて解きます。構造は次の通りです。

dp[ i ][ j ]:
料理 i まで考えたときに
合計の調理時間が j となる組み合わせが存在する
（存在する：１、存在しない：０）

これを、全ての料理について考えてあげれば一つのオーブンで実現可能な調理時間がわかります。遷移は次の通りです。

１）料理 i を選ぶ（調理 i の時間は T[i]）

dp[ i ][ j ]が1ならばdp[ i+1 ][ j+T[ i ] ]を１にする。

２）料理 i を選ばない

dp[ i ][ j ]が1ならばdp[ i+1 ][ j+T[ i ] ]を１にする。

ここで、dp[i][j]が1ならばという条件は

dp[i+1][j] = dp[ i+1 ][ j ] | dp[ i ][ j ] 

とすれば実現できます。「 | 」はOR演算です。
（2次元化かつ２）→１）の順番で更新すれば代入しても大丈夫です）。

小さな例で遷移を示してみました。初期状態はdp[0][0] = 1です。0個選んだ（一個も料理を見ていない状態では、時間０だけ実現可能ということです。）

次に、時間の範囲に関してです。本問題では

n≦100,
Ti ≦1000

ですので、最大ケースでは

10^5

の値が出現します。ということで、dpの j は0から10^5までの範囲を回しておけば全部の調理時間を網羅できます。

dpによる探索が終わりましたら、

dp[ n ][ k ]

には、全ての料理を考慮した際に、その時間 k が実現できるかどうかという情報が入っています。冒頭にも述べましたが、選んでいない料理の調理時間 k' は 

k' = 全ての料理の調理時間 - k

と求まりますので、kとk'の大きいほうが、全体の調理時間となります。実現可能な全ての k に対してこの計算を行い、そのうちの最小値が求める答えとなります。

実装

 #include <bits/stdc++.h> #define  rep(i,n) for(int i=0;i<n;++i) #define  reps(i,s,n) for(int i=s;i<n;++i)
using namespace std;
using ll = long long;
using P = pair<int, int>;

const int M = 1e5;
int main()
{
   int n;
   cin >> n;
   vector<int> t(n);
   rep(i, n) cin >> t[i];
   int sum = 0;
   rep(i, n) sum += t[i];

   //for文でMまで探索するので、M+1000でもはみ出さないようにする。
   vector<vector<int>> dp(n + 5, vector<int>(M+1005));

   dp[0][0] = 1;
   rep(i, n)
   {
       rep(j, M)
       {
           dp[i + 1][j] = dp[i][j] | dp[i + 1][j];
           dp[i + 1][j + t[i]] = dp[i][j] | dp[i + 1][j + t[i]];
       }
   }
   int ans = M;
   rep(i, M)
   {
       if (dp[n][i] == 1)
       {
           int a = i;
           int b = sum - i;
           ans = min(ans, max(a, b));
       }
   }
   cout << ans << endl;

   return 0;
}

あとがき

dpの問題でした。といいますか、数列の部分列の和の問題でした。今回のようにdpを使えば解けますし、1e5までの数しか登場しないことを用いれば、枝刈りしながらDFSなどでも求めることができます。

間違っても、貪欲に詰めていくということはしないようにしましょう。

また、本問題では2次元のdpで解きましたが、1次元にすることも可能です。このとき、時間の大きいほうから更新することにより循環参照を避けることが可能です。更新部分だけ紹介しておくので、インライン化の練習がしたい方はぜひやってみてください。これは知識というよりかは慣れの部分が大きいので、興味があればとりあえずやってみるぐらいの気持ちでいると、いつかすんなりと実装できるようになると思います。

rep(i, n)
{
    for(int j=M; j>=0 ;--j)
    {
        dp[j + t[i]] = dp[j] | dp[j + t[i]];
    }
}

こうみると、とてもシンプルなdpで表現できるんですね。驚きです。