Educational DP Contest D問題, E問題

レッドコーダーが教える、競プロ・AtCoder上達のガイドライン【中級編：目指せ水色コーダー！】

前回の続き

全探索：全列挙, 工夫して通り数を減らす全列挙, ビット全探索

解説

動的計画法超入門！ Educational DP Contest の A ～ E 問題の解説と類題集

D問題

D - Knapsack 1

C++

#include<iostream>
#include<vector>
#include<algorithm>
#include<iomanip>
#include<utility>
#include<iomanip>
#include<map>
#include<queue>
#include<stack>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<cctype>

#define rep(i,n) for(int i=0; i<(n); ++i)
#define fixed_setprecision(n) fixed << setprecision((n))
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9

using namespace std;
using ll =long long;
using P = pair<int,int>;
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; }
const long long INF = 1LL << 60;

ll dp[101][100001];
ll w[101];
ll v[101];
ll N, W;

ll dfs(ll i, ll j){
    if(dp[i][j] >= 0) return dp[i][j];

    ll res = 0;
    if(N==i){
        res = 0;
    }else if(j < w[i]){
        res = dfs(i+1, j);
    }else{
        res = max(dfs(i+1, j), dfs(i+1, j-w[i]) + v[i]);
    }
    return dp[i][j] = res;
}

int main(int argc, const char * argv[]) {
    cin >> N >> W;

    rep(i, N){
        cin >> w[i] >> v[i];
    }
    memset(dp, -1, sizeof(dp));
    cout << dfs(0, W) << endl;

    return 0;
}

C++

#include <bits/stdc++.h>

#define rep(i,n) for(int i=0; i<(n); ++i)
#define fixed_setprecision(n) fixed << setprecision((n))
#define execution_time(ti) printf("Execution Time: %.4lf sec\n", 1.0 * (clock() - ti) / CLOCKS_PER_SEC);
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9

using namespace std;
using ll =long long;
using P = pair<int,int>;
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; }
const long long INF = 1LL << 60;

ll dp[110][100010];

int main(int argc, const char * argv[]) {
    int n, w;
    cin >> n >> w;

    vector<int> w_list(n);
    vector<int> v_list(n);

    rep(i, n) cin >> w_list[i] >> v_list[i];

    for(int i=0; i<n; i++){
        for(int sum_w=0; sum_w <= w; sum_w++){
            if(sum_w - w_list[i] >= 0){
                chmax(dp[i+1][sum_w], dp[i][sum_w - w_list[i]] + v_list[i]);
            }
            chmax(dp[i+1][sum_w], dp[i][sum_w]);
        }
    }
    cout << dp[n][w] << endl;

    return 0;
}

A - コンテスト

C++

#include <bits/stdc++.h>

#define rep(i,n) for(int i=0; i<(n); ++i)
#define fixed_setprecision(n) fixed << setprecision((n))
#define execution_time(ti) printf("Execution Time: %.4lf sec\n", 1.0 * (clock() - ti) / CLOCKS_PER_SEC);
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9

using namespace std;
using ll =long long;
using P = pair<int,int>;
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; }
const long long INF = 1LL << 60;

bool dp[110][10010];

int main() {
    int n;
    cin >> n;

    vector<int> p(n+1);
    int sum_value=0;
    rep(i, n){
        cin >> p[i+1];
        sum_value += p[i+1];
    }

    dp[0][0]=true;

    for(int i=1; i<=n; i++){
        for(int j=0; j<=sum_value; j++){
            if(dp[i-1][j]){
                dp[i][j]=true;
                dp[i][j+p[i]]=true;
            }
        }
    }

    int res=0;
    for(int i=0; i<=sum_value; i++){
        if(dp[n][i]) res++;
    }
    cout << res << endl;
    return 0;
}

D - サイコロ

C++

#include <bits/stdc++.h>

#define rep(i,n) for(int i=0; i<(n); ++i)
#define fixed_setprecision(n) fixed << setprecision((n))
#define execution_time(ti) printf("Execution Time: %.4lf sec\n", 1.0 * (clock() - ti) / CLOCKS_PER_SEC);
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9

using namespace std;
using ll =long long;
using P = pair<int,int>;
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; }
const long long INF = 1LL << 60;

double dp[102][64][64][64];
int main(int argc, const char * argv[]) {
    int n;
    ll d;
    cin >> n >> d;

    int cnt_2 = 0, cnt_3 = 0, cnt_5 = 0;
    while (d % 2 == 0) {
        d /= 2;
        cnt_2++;
    }
    while (d % 3 == 0) {
        d /= 3;
        cnt_3++;
    }
    while (d % 5 == 0) {
        d /= 5;
        cnt_5++;
    }
    if(d != 1){ cout << 0 << endl; return 0; }

    dp[0][0][0][0]=1;
    for(int i=0; i<n; i++){
        for(int j=0; j<=cnt_2; j++){
            for(int k=0; k<=cnt_3; k++){
                for(int l=0; l<=cnt_5; l++){
                    int j1 = min(j + 1, cnt_2);
                    int j2 = min(j + 2, cnt_2);
                    int k1 = min(k + 1, cnt_3);
                    int l1 = min(l + 1, cnt_5);
                    dp[i+1][j ][k ][l ] += dp[i][j][k][l] / 6;
                    dp[i+1][j1][k ][l ] += dp[i][j][k][l] / 6;
                    dp[i+1][j ][k1][l ] += dp[i][j][k][l] / 6;
                    dp[i+1][j2][k ][l ] += dp[i][j][k][l] / 6;
                    dp[i+1][j ][k ][l1] += dp[i][j][k][l] / 6;
                    dp[i+1][j1][k1][l ] += dp[i][j][k][l] / 6;
                }
            }
        }
    }
    cout << fixed_setprecision(9) << dp[n][cnt_2][cnt_3][cnt_5] << endl;
    return 0;
}

E問題

E - Knapsack 2

C++

#include <bits/stdc++.h>

#define rep(i,n) for(int i=0; i<(n); ++i)
#define fixed_setprecision(n) fixed << setprecision((n))
#define execution_time(ti) printf("Execution Time: %.4lf sec\n", 1.0 * (clock() - ti) / CLOCKS_PER_SEC);
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9

using namespace std;
using ll =long long;
using P = pair<int,int>;
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; }
const long long INF = 1LL << 60;

ll dp[110][100010];

int main(int argc, const char * argv[]) {
    int n, w;
    cin >> n >> w;

    vector<int> w_list(n);
    vector<int> v_list(n);
    ll max_v = 0;
    rep(i, n){
        cin >> w_list[i] >> v_list[i];
        max_v += v_list[i];
    }

    rep(i, 110) rep(j, 100010) dp[i][j] = INF;
    dp[0][0] = 0;

    for(int i=0; i<n; i++){
        for(int sum_v=0; sum_v<=max_v; sum_v++){
            if(sum_v - v_list[i] >= 0){
                chmin(dp[i+1][sum_v], dp[i][sum_v - v_list[i]] + w_list[i]);
            }
            chmin(dp[i+1][sum_v], dp[i][sum_v]);
        }
    }

    ll res = 0;
    for(int sum_v=0; sum_v<=max_v; sum_v++){
        if(dp[n][sum_v] <= w) if(res < sum_v) res = sum_v;
    }
    cout << res << endl;

    return 0;
}