ABC145 E - All-you-can-eat

May 6, 2020

競技プログラミング

AtCoder, DP

問題

問題リンク

考えたこと(WA)

最後の1つをT-1に取ると決めてしまえば、N-1(最後にとる1つを除く残りの料理)で食べ終わるのにT-1かかる美味しさの最大値というナップサック問題に落とし込めそう。
計算量はO(NT)でO(10^6)なので間に合う

あとは最後に食べる奴は一番美味しさがでかい奴でいいかな？

これは嘘解
以下のような入力でWAになる

上記の解法だと, 最後に2 40を食べるとなって、T-1(=999)で残りの2つを食べるということになるが、これだと残り1つのどちらかが食べれなくなってしまう。
最後に500 20を食べてしまえば、T-1(=999)で残りの2つも食べれて全部食べれる

解説を見て

最後に食べるのは一意には特定できないので、全探索する。
しかし最後に食べるのを全探索して、さらに残りのやつでT-1までに食べれる最大値を求めるとO(10^3 * 10^3 * 10^3)でTLEになってしまう。

予めDPテーブルを作成しておけば、計算量を落とすことができる。
ここでDPテーブルを2つ用意する必要がある。

DP1[i][j] : 0~i番目までの料理の中で食べ終わるのにj分かかるので最大の満足度
DP2[i][j] : i~N番目までの料理の中で食べ終わるのにj分かかるので最大の満足度

これを用意しておいて、全ての料理を全探索していく
i番目の料理をT-1分に食べる時の満足度はDP1[i-1][j]とDP[i+1][t-1-j]とi番目の料理の満足度の和となる(jは0~T)

これで全ての料理を全探索してあげればO(NT)=O(10^6)で計算できる

提出したコード

提出リンク

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for (ll i = 0; i < (ll)(n); ++i)
#define erep(i, n) for (ll i = 0; i <= (ll)(n); ++i)
#define FOR(i,a,b) for (ll i = (a); i < (ll)(b); ++i)
#define EFOR(i,a,b) for (ll i = (a); i <= (ll)(b); ++i)

void chmax(ll& a, ll b) { a = max(a, b); }
void chmin(ll& a, ll b) { a = min(a, b); }

using P = pair<int, int>;

int main() {
    int n,t; cin >> n >> t;
    vector<P> ba;
    rep(i, n) {
        int a,b;
        cin >> a >> b;
        ba.push_back(make_pair(b,a));
    }
    vector<vector<int>> dp1(n+1, vector<int>(t, 0));
    vector<vector<int>> dp2(n+1, vector<int>(t, 0));

    vector<int> ans1(n,0);
    vector<int> ans2(n,0);
    rep(i, n) {
        rep(j, t) {
            if(j >= ba[i].second) {
                if(i > 0) dp1[i][j] = max(dp1[i-1][j-ba[i].second] + ba[i].first, dp1[i-1][j]);
                else dp1[i][j] = ba[i].first;
            } else {
                if(i > 0) dp1[i][j] = dp1[i-1][j];
            }
            ans1[i] = max(ans1[i], dp1[i][j]);
        }
    }

    for(int i=n-1; i >= 0; i--) {
        rep(j, t) {
            if(j >= ba[i].second) {
                dp2[i][j] = max(dp2[i+1][j-ba[i].second] + ba[i].first, dp2[i+1][j]);
            } else {
                dp2[i][j] = dp2[i+1][j];
            }
            ans2[i] = max(ans2[i], dp2[i][j]);
        }
    }

    int ans = 0;
    rep(i, n) {
        int tmpans = 0;
        rep(j, t) {
            if(i == 0) {
                tmpans = max(tmpans, dp2[i + 1][j]);
            } else if(i == n-1) {
                tmpans = max(tmpans, dp1[i - 1][j]);
            } else {
                tmpans = max(tmpans, dp1[i - 1][j] + dp2[i + 1][t - 1 - j]);
            }
        }
        ans = max(ans, tmpans+ba[i].first);
    }

    cout << ans << endl;
    return 0;
}

解説動画を見て

https://www.youtube.com/watch?v=aDDV_WBwzTM

ちょっと工夫すればDPテーブル1つで済む
ある料理の組み合わせ(最後の注文がT-1以下になる)は、並び替えができて最後の注文は食べるのに一番時間がかかる料理で固定できる。

これをすると、最後に食べる料理にかかる時間がj分かかるときの満足度は
食べるのにかかる時間がjより小さい料理の中でT-1分までに食べ終わる中での最大の満足度と最後に食べる料理の満足度の和になる

入力を食べるのにかかる時間の昇順ソートで並べておくと
i番目の料理を最後に食べるとしたら、i-1までの中での料理の中でT-1分までに食べ終わる中での最大の満足度を求めてあげればいい
(つまり, 1つ前の解法でのDP1, DP2のうちDP1だけあればいい)

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for (ll i = 0; i < (ll)(n); ++i)
#define erep(i, n) for (ll i = 0; i <= (ll)(n); ++i)
#define FOR(i,a,b) for (ll i = (a); i < (ll)(b); ++i)
#define EFOR(i,a,b) for (ll i = (a); i <= (ll)(b); ++i)
#define chmax(x,y) x = max(x,y);
#define chmin(x,y) x = min(x,y);



using P = pair<int, int>;

int dp[3005][3005];

int main() {
    int n,t; cin >> n >> t;
    vector<P> ab(n);
    rep(i, n) cin >> ab[i].first >> ab[i].second;

    // 一番時間がかかるのを最後に食べるという方針にする
    // 昇順ソートしておけば、i番目を最後に食べるときに、i-1まででt-1までに食べれる最大量を求めるので済む
    sort(ab.begin(), ab.end());
    int ans = 0;
    rep(i, n) {
        rep(j, t) {
            chmax(dp[i+1][j], dp[i][j]);
            int nj = j+ab[i].first;
            if(nj < t) chmax(dp[i+1][nj], dp[i][j] + ab[i].second);
        }
        int now = dp[i][t-1] + ab[i].second;
        chmax(ans, now);
    }
    cout << ans << endl;
    return 0;
}