AtCoder Regular Contest 042 C - おやつ

問題

　種類のおやつについてそれぞれ値段と満足度が設定されており、各種類について多くとも1つ持っていくことができる。どの1つのおやつについてもそのおやつがなければ合計で円以下になるとき持っていくことが可能である場合に、満足度の最大値を求めよ。

解法

　あるおやつ集合の中で一番値段が小さいもの一つを除いた値段の和を考えると、他のおやつを除いた場合は必ず以下になるため、が以下であるかどうかを考えればよい。

　(あるおやつを除いたとして)残りのおやつから値段が以下となるように満足度を最大化することはDPでできる。

　値段を降順にソートしてからDPテーブルを作れば、答えを求めるときに各おやつに対して同じテーブルを使うことができる。よってでこの問題が解ける。

反省

　1時間28分(6WA)でAC。最初考えた方針がかなり想定解に近かったが、というような最悪で100倍遅いものを考えていたし、実装も間違っていてWA。その後もmapを使って高速化できるんじゃないかとか意味不明なことを考え出してTLEやWAなどを次々出していく。結局1時間経ってしまったので解説スライドを見た。1ページ。超短い。見た後も実装にちょっと苦労してしまったがなんとかAC。終わってみれば簡単な問題で、なんでこれが解けないのか。もっと考察で簡単に書けるコードを思い浮かべれれるようにならなければ。

コード

#include"bits/stdc++.h"
using namespace std;
using ll = int64_t;

int main() {
    ll N, P;
    cin >> N >> P;

    struct Snack {
        ll a, b;
    };

    vector<Snack> snacks(N);
    for (ll i = 0; i < N; i++) {
        cin >> snacks[i].a >> snacks[i].b;
    }

    sort(snacks.begin(), snacks.end(), [&](Snack& lhs, Snack& rhs){
        return lhs.a != rhs.a ? lhs.a > rhs.a : lhs.b > rhs.b;
    });

    //dp[i][j] := i番目まで見てj円以下の場合の最大幸福度
    vector<vector<ll>> dp(N, vector<ll>(P + 1, 0));

    for (ll i = 0; i < N; i++) {
        for (ll j = 0; j <= P; j++) {
            //i番目を持っていかない
            dp[i][j] = max(dp[i][j], (i == 0 ? 0 : dp[i - 1][j]));

            //i番目を持っていく
            ll p = j + snacks[i].a;
            if (p > P) {
                continue;
            }
            dp[i][p] = max(dp[i][p], (i == 0 ? 0 : dp[i - 1][j]) + snacks[i].b);
        }
    }

    ll ans = (snacks[0].a <= P ? snacks[0].b : 0);
    for (ll i = 1; i < N; i++) {
        ans = max(ans, dp[i - 1][P] + snacks[i].b);
    }

    cout << ans << endl;
}