ABC204 D-Cooking(C++)

問題概要

問題文

料理$1$から$N$の$N$品の料理を作る。
料理$i$は、オーブンを連続して$T_i$分間使うことで作れる。$1$つのオーブンを$2$つ以上の料理のために同時に使うことはできない。
$2$つのオーブンを使えるとき、$N$品の料理を全て作るまでに最短で何分かかるか?

制約

• $1\leq N\leq 100$
• $1\leq T_i\leq 10^3$
• 入力はすべて整数

問題リンク

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

解法

言い換えると、次の通り。

• $\{1,2,\dots,N\}=X \cup Y$と分割する
• $\max(\sum_{i\in X}{T_i},\sum_{i\in Y}{T_i})$を最小化せよ。

以下$S_X=\sum_{i\in X}{T_i}$,$S_Y=\sum_{i\in Y}{T_i}$,$S=\sum_{i=1}^{N}{T_i}$とします。


この問題の重要なポイントとして、$X,Y$について、知りたいのはそれぞれ$S_X,S_Y$のみということがあります。これは、最小化する式が$S_X,S_Y$のみで表されるからです。
もっと言うと、$S_Y=S-S_X$なので、$S_X$が分かれば$S_Y$も自動的にわかります。したがって、$S_X$を決め打って調べていこうという方針が立ちます。
$S_X$に対応する$X$がそもそも存在しないかもしれないということに注意しましょう。これは、部分和問題の要領で解決できます。


まとめると、次のようにすればいいです。

• あらかじめ、$T$についての部分和問題を解いておく。
• $S_X=0,1,\dots,S$に対して、以下を繰り返す
• • 対応する$X$が存在しなければスキップ
• • $S_Y=S-S_X$について、$ans=\min(ans,\max(S_X,S_Y))$と更新する

実装

計算量$O(NS)$です。

main.cpp

#include<iostream>
#include<vector>
using namespace std;
int main(){
    int n;
    cin>>n;
    vector<int> t(n);
    for(int i=0;i<n;i++)cin>>t[i];
    int S=0;
    for(int i=0;i<n;i++)S+=t[i];
    //部分和問題を解いておく
    //dp[i][j]:=先頭i項をみる。いくつか選んで和をjにできるか?
    vector<vector<bool>> dp(n+1,vector<bool>(S+1,false));
    dp[0][0]=true;
    for(int i=0;i<n;i++)for(int j=0;j<=S;j++){
        if(!dp[i][j])continue;  //dp[i][j]=falseなら、dp[i][j]からの遷移は起きない

        dp[i+1][j]=true;    //t_iを選ばない場合
        dp[i+1][j+t[i]]=true;   //選ぶ場合
    }
    const int inf=1e9;
    int ans=inf;
    for(int sx=0;sx<=S;sx++){
        if(!dp[n][sx])continue; //作れないならcontinue
        int sy=S-sx;
        int time=max(sx,sy);    //全体でかかる時間
        ans=min(ans,time);
    }
    cout<<ans<<endl;
}

• AC:22ms