Cooking [AtCoder Beginner Contest 204 D]

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

解説

https://atcoder.jp/contests/abc204/submissions/23262989

この問題はDPで解ける。
いかにDPで解くという所に帰着させるかを説明していこう。

まず、制約がとても小さい。
パッと見て貪欲で行けそうな感じがあるが、貪欲ならもうちょっと制約が大きくても解けるので、
ギリギリを目指す問題設定という方針を考えると怪しい。
一旦、一般的なアルゴリズムの形に落とし込めないか考えてみよう。

正直もうこの時点で、最短というのとか、制約があまり大きくないとか、今までの経験とかでDP感がしている。

性質を見つける

最終的にはとある料理はどちらかのオーブンに割り当てられることになる。
かつ、料理がオーブンに割り当てられているときに、とあるオーブンが料理がどのような順番で調理されても最終的な最短時間は変わらない。
つまり、選択肢としては料理はどちらかに割り当てられているかだけが関係していて割り当て順番は関係ないことが分かる。
なので、適切に2グループに分けて、大きい方を最小化する問題に帰着できる。

DP

dp[i][t] := i番目まで料理作成が終わっていて、オーブンAの使用時間がtであるときのオーブンBの使用時間の最小値

本番はこのDPで解いたが、何番目まで料理作成が終わっていて、オーブンAの使用時間が分かっていればオーブンBの使用時間は一意に定まるので、最小値もなにもない。
なので、特にメモる必要もないのだが、書いてしまったので、これで説明する。

遷移は、料理作成時にオープンAを使うなら、dp[i][t] -> dp[i + 1][t + A[i]]と遷移させる。
オーブンBを使うなら、dp[i][t] + A[i] -> dp[i + 1][i]と遷移させる。

最後はmax(t, dp[N][t])の最小値を取れば答え。

int N, T[101];
int dp[101][102010];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(i, 0, N) cin >> T[i];

    rep(i, 0, N + 1) rep(t, 0, 101010) dp[i][t] = inf;
    dp[0][0] = 0;
    rep(i, 0, N) rep(t, 0, 101010) if (dp[i][t] != inf) {
        chmin(dp[i + 1][t + T[i]], dp[i][t]);
        chmin(dp[i + 1][t], dp[i][t] + T[i]);
    }

    int ans = inf;
    rep(t, 0, 101010) chmin(ans, max(t, dp[N][t]));
    cout << ans << endl;
}