atcoder beginner contest 219 D問題 配るDPが更新されない

Question

前提・実現したいこと

ABC219D問題を解いたのですが、以下のコードを試したところ答えがINFの値のままで更新されません。今回配るDPが模範解答で使われていたので、貰うDPでも試したのですが、なぜ貰うDPでは不正解になるのかわかりません。原因を教えていただけると幸いです。

発生している問題・エラーメッセージ

入力サンプル
3
5 6
2 1
3 4
2 3
を与えると、2と返すべきところと-1と返してしまう。

該当のソースコード

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;

const int INF = 1e9;

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
template <typename Type> inline string toString(const Type &a){ostringstream oss; oss << a; return oss.str();}

class Dsu{
public:
    vector <ll> par; 
    vector <ll> siz; 

    Dsu(ll sz_): par(sz_), siz(sz_, 1LL) {
        for (ll i = 0; i < sz_; ++i) par[i] = i; 
    }
    void init(ll sz_) {
        par.resize(sz_);
        siz.assign(sz_, 1LL); 
        for (ll i = 0; i < sz_; ++i) par[i] = i; 
    }

    ll find(ll x) { 
        while (par[x] != x) {
            x = par[x] = par[par[x]]; 
        }
        return x;
    }

    bool merge(ll x, ll y) {
        x = find(x);
        y = find(y);
        if (x == y) return false;
        if (siz[x] < siz[y]) swap(x, y);
        siz[x] += siz[y];
        par[y] = x;
        return true;
    }

    bool issame(ll x, ll y) { 
        return find(x) == find(y);
    }

    ll size(ll x) { 
        return siz[find(x)];
    }
};
int N, X, Y;
vector<int> A, B;
vector<vector<vector<int>>> dp;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> N >> X >> Y;
    A.resize(N); 
    B.resize(N);
    for(int i = 0; i < N; ++i) cin >> A[i] >> B[i];
    dp.assign(N + 1, vector<vector<int>>(X + 1, vector<int>(Y + 1, INF)));
    dp[0][0][0] = 0;
    for(int i = 0; i < N; ++i){
        for(int j = 0; j <= X; ++j){
            for(int k = 0; k <= Y; ++k){
                if(j - A[i] >= 0 && k - B[i] >= 0){
                    dp[i + 1][j][k] = min(dp[i][j][k], dp[i][j - A[i]][k - B[i]] + 1);
                }
                dp[i + 1][j][k] = min(dp[i + 1][j][k], dp[i][j][k]);
            }
        }
    }
    cout << (dp[N][X][Y] == INF ? -1 : dp[N][X][Y]) << endl;
}

###試したこと(追記:10/1)
この方のコードを参考にし、以下のような配列の再利用を使わず貰うDPを作成しました。するとACされたのですが、元のコードとやっていることが同じに見えるのですが、なぜ結果が異なるのでしょうか。その点も教えていただけると幸いです。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;

const int INF = 1e9;


int N, X, Y;
vector<int> A, B;
vector<vector<vector<int>>> dp;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);  
    cin >> N >> X >> Y;
    A.resize(N); 
    B.resize(N);
    for(int i = 0; i < N; ++i) cin >> A[i] >> B[i];
    dp.assign(N + 1, vector<vector<int>>(X + 1, vector<int>(Y + 1, INF)));
    dp[0][0][0] = 0;
    for(int i = 0; i < N; ++i){
        for(int j = 0; j <= X; ++j){
            for(int k = 0; k <= Y; ++k){
                dp[i + 1][j][k] = min(dp[i][max(j - A[i], 0)][max(k - B[i], 0)] + 1, dp[i][j][k]);
            }
        }
    }
    cout << (dp[N][X][Y] == INF ? -1 : dp[N][X][Y]) << endl;
}

補足情報（FW/ツールのバージョンなど）

DPは模範解答と同じく
DP[i + 1][j][k] = i番目までの弁当からj個のたこ焼きとk個のたいやきを揃えるための最小の弁当の数
と定義しました。

Answer 1

ちょうどX個、Y個買う場合しか考慮されてないからです。
サンプルのケースだとちょうど5個と6個買うパターンがないので、解なしとなります。

Comments

[rdld036]

dp[i + 1][j][k] = min(dp[i][max(j - A[i], 0)][max(k - B[i], 0)] + 1, dp[i][j][k]);
このようにすることで各dp[i][j][k]の値がピッタリだけでなく、j個以上、k個以上の場合も加味された値になり正しい答えが得られるということでしょうか。

[yudedako67]

そうです