AtCoderBeginnerContest410の解説＆感想です。
コンテストリンク

問題一覧

E問題 - Battles in a Row

問題リンク

問題概要

二つの整数$H,M$と、長さ$N$の二つの数列$A_1,A_2,...,A_N$、$B_1,B_2,...,B_N$が与えられる。$i$を$1$から$N$まで増やしながら、以下の操作を繰り返す。

$A_i$か$B_i$のどちらか一方を選ぶ
- $A_i$を選んだ場合：$H$を$A_i$減らす
- $B_i$を選んだ場合：$M$を$B_i$減らす

$H \ge 0$かつ$M \ge 0$を満たしたまま到達できる最大の$i$を求めよ。

制約

$1 \le N \le 3000$
$1 \le H,M \le 3000$
$1 \le A_i,B_i \le 3000$

考察

いかにもDPみたいな問題なので、うまくDPできないか考える。（DPに見せかけて貪欲で上手く解けるみたいな場合もあるから難しいところ...）
とりあえず

$dp[i][j][k] := i番目まで到達して、H残量をj以上、M残量をk以上にできるか？$

とすれば答えは出そう。答えは出そうだけど、これだと三次元DPになって$O(N^3)$なので、次元を落としたい。どうしよう。
よく考えてみると、「$i$番目に到達できるか？」という問題は、$i$番目まで到達して$H$残量がjだった時の最大の$M$残量がわかっていれば判定できそうなことに気づいた。
ということで、DPテーブルを

$ dp[i][j] := i番目まで到達して、H残量がjの時の最大のM残量 $

とすれば良さそう。
計算量はDPテーブルを順次$O(1)$で更新していけばいいので、$O(N^2)$。

実装

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vll = vector<ll>;
using vvll = vector<vll>;
bool chmax(ll &a, ll b){
    if(a < b){
        a = b;
        return true;
    }
    return false;
}
int main(void){
    //入力
    ll N,H,M;
    cin>>N>>H>>M;
    vll A(N), B(N);
    for(int i=0;i<N;i++) cin>>A[i]>>B[i];
    
    //dp[i][j] := iまで到達して、H残量がjの時のM残量の最大
    vvll dp(N, vll(H+1, -10000000LL));
    dp[0][H] = M-B[0];
    if(H-A[0] >= 0) dp[0][H-A[0]] = M;
    for(int i=1;i<N;i++){
        for(int j=0;j<=H;j++){
            //Aを選ぶ
            if(j+A[i] <= H) chmax(dp[i][j], dp[i-1][j+A[i]]);
            //Bを選ぶ
            chmax(dp[i][j], dp[i-1][j]-B[i]);
        }
    }
    
    //iを逆から見て、最初に到達できるiを表示
    for(int i=N-1;i>=0;i--){
        for(int j=0;j<=H;j++){
            if(dp[i][j] >= 0){
                cout<<i+1<<endl;
                return 0;
            }
        }
    }
    //到達できるiがひとつもなければ0
    cout<<0<<endl;
}

その他問題