はじめに

今回は、39から45の7問解きました！ちゃんとcopilotなしでやりました(当たり前)

39　JOI 2011 予選 4 - 1 年生

問題はこちらです！
問題文↓

数列が与えられ、その間に+か-を入れていく
途中、「0未満になる」または「20を超える」ことのない式は何通りか

これは、縦N-1(数列の間の個数)、横21(0を含む)のDPを作成しました
もし、0未満、20を超えることがでたらDPに書き込まないようにすれば終わりです
コードはこんな感じです

#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define Rep(i, n, a) for (int i = (a); i < (n); ++i)
#define All(a) (a).begin(), (a).end()
#define YesNo(b) ((b) ? "Yes" : "No")
using LL = long long;
string alphabet = "abcdefghijklmnopqrstuvwxyz";
string ALPHABET = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
int smallMOD = 998244353;
int bigMOD = 1000000007;

int main()
{
    int n;
    cin >> n;
    vector<int> A(n);
    rep(i,n) cin>>A[i];
    vector<vector<LL>> dp(n-1,vector<LL>(21));
    dp[0][A[0]] = 1;
    rep(i,n-2){
        rep(j,21){
            if(j-A[i+1]>=0){
                dp[i+1][j-A[i+1]]+=dp[i][j];
            }
            if(j+A[i+1]<=20){
                dp[i+1][j+A[i+1]]+=dp[i][j];
            }
        }
    }
    cout << dp[n-2][A.back()] << endl;
    return 0;
}

40　JOI 2012 予選 4 - パスタ

問題はこちらです！
問題文↓

3種類のパスタがある
3日以上同じパスタが来ないようにN日間パスタを食べるには何通りの方法があるか

3次の配列のDPです！
DP[i][j][k]として、、、
i:n日間
j:3種類のパスタ
k:連続した日数(2日まで)
となり、DP[n][3][2]を作成しました
コードはこんな感じです

#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (ll i = 0; i < (n); ++i)
#define rep1(i, n) for (ll i = 1; i < (n); ++i)
#define rrep(i, n) for (ll i = n; i > 0; --i)
#define bitrep(i, n) for (ll i = 0; i < (1 << n); ++i)
#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()
#define yesNo(b) ((b) ? "Yes" : "No")
using ll = long long;
using ull = unsigned long long;
using ld = long double;
string alphabet = "abcdefghijklmnopqrstuvwxyz";
string ALPHABET = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
const double pi = 3.141592653589793;
ll smallMOD = 998244353;
ll bigMOD = 1000000007;

// 0,1,2のリストからx以外の数字のペアを返す.
pair<int, int> f(int x)
{
    if (x == 0)
    {
        return make_pair(1, 2);
    }
    else if (x == 1)
    {
        return make_pair(0, 2);
    }
    else
    {
        return make_pair(0, 1);
    }
}

int main()
{
    int n, m;
    cin >> n >> m;
    vector<int> A(120, -1);
    rep(i, m)
    {
        int a, b;
        cin >> a >> b;
        A[a - 1] = b - 1;
    }
    vector<vector<vector<int>>> dp(n, vector<vector<int>>(3, vector<int>(2, 0)));
    if (A[0] == -1)
    {
        dp[0][0][0] = 1;
        dp[0][1][0] = 1;
        dp[0][2][0] = 1;
    }
    else
    {
        dp[0][A[0]][0] = 1;
    }
    rep1(i, n)
    {
        if (A[i] == -1)
        {
            // 計15本の遷移.
            rep(j, 3)
            {
                auto p = f(j);
                dp[i][j][0] += dp[i - 1][p.first][0] + dp[i - 1][p.first][1] + dp[i - 1][p.second][0] + dp[i - 1][p.second][1];
                dp[i][j][0] %= 10000;
            }
            rep(j, 3)
            {
                dp[i][j][1] += dp[i - 1][j][0];
                dp[i][j][1] %= 10000;
            }
        }
        else
        {
            // 計5本の遷移.
            dp[i][A[i]][1] += dp[i - 1][A[i]][0];
            dp[i][A[i]][1] %= 10000;
            auto p = f(A[i]);
            dp[i][A[i]][0] += dp[i - 1][p.first][0] + dp[i - 1][p.first][1] + dp[i - 1][p.second][0] + dp[i - 1][p.second][1];
            dp[i][A[i]][0] %= 10000;
        }
    }
    ll ans = 0;
    rep(i, 3)
    {
        ans += dp[n - 1][i][0] + dp[n - 1][i][1];
        ans %= 10000;
    }
    cout << ans << endl;
    return 0;
}

ちょっと慣れてきた！

41　JOI 2013 予選 4 - 暑い日々

問題はこちらです！
問題文↓

服の着ることができる"気温"と服の"派手さ"と、毎日の気温が与えられる
毎日の服を選ぶ時、1日前と今日との服の派手さの差の絶対値が最大になるように着ていきたい
この派手さの最大のコストを求めてください
ただし、服の気温に適した気温で無いと着ることが出来ません

DP[i][j]とすると、、、
i:D日間の派手さのステート
j:N種類の服のステート
のようにDP[D][N]を作成しました！
コードはこんな感じです

#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (ll i = 0; i < (n); ++i)
#define rep1(i, n) for (ll i = 1; i < (n); ++i)
#define rrep(i, n) for (ll i = n; i > 0; --i)
#define bitrep(i, n) for (ll i = 0; i < (1 << n); ++i)
#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()
#define yesNo(b) ((b) ? "Yes" : "No")
using ll = long long;
using ull = unsigned long long;
using ld = long double;
string alphabet = "abcdefghijklmnopqrstuvwxyz";
string ALPHABET = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
const double pi = 3.141592653589793;
ll smallMOD = 998244353;
ll bigMOD = 1000000007;

bool canWear(ll a, ll b, ll t)
{
    return a <= t && b >= t;
}

int main()
{
    ll D, N;
    cin >> D >> N;
    vector<ll> T(D);
    rep(i, D) cin >> T[i];
    vector<vector<ll>> ABC(N, vector<ll>(3));
    rep(i, N) cin >> ABC[i][0] >> ABC[i][1] >> ABC[i][2];
    vector<vector<ll>> dp(D, vector<ll>(N, 0));
    rep1(i, D)
    {
        rep(j, N)
        {
            if (canWear(ABC[j][0], ABC[j][1], T[i - 1]))
            {
                rep(k, N)
                {
                    dp[i][k] = max(dp[i][k], dp[i - 1][j] + abs(ABC[j][2] - ABC[k][2]));
                }
            }
        }
    }
    ll ans = 0;
    rep(i, N)
    {
        if (canWear(ABC[i][0], ABC[i][1], T[D - 1]))
            ans = max(ans, dp[D - 1][i]);
    }
    cout << ans << endl;
    return 0;
}

だいぶ慣れてきた！

42　JOI 2015 予選 4 - シルクロード

問題はこちらです！
問題文↓

街を移動するのに2つの選択がある
・コストをかけて次の街へ移動する
・コストを掛けずに待機する
毎日コストが変わっていく時、最小のコストの値を出力してください

DP[m+1]n+1を作って、DP[i+1]jとDP[i+1]j+1を書き換えていきます
コードはこんな感じです

#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (ll i = 0; i < (n); ++i)
#define rep1(i, n) for (ll i = 1; i < (n); ++i)
#define rrep(i, n) for (ll i = n; i > 0; --i)
#define bitrep(i, n) for (ll i = 0; i < (1 << n); ++i)
#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()
#define yesNo(b) ((b) ? "Yes" : "No")
using ll = long long;
using ull = unsigned long long;
using ld = long double;
string alphabet = "abcdefghijklmnopqrstuvwxyz";
string ALPHABET = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
const double pi = 3.141592653589793;
ll smallMOD = 998244353;
ll bigMOD = 1000000007;

int main()
{
    int n, m;
    cin >> n >> m;
    vector<int> D(n), C(m);
    rep(i, n) cin >> D[i];
    rep(i, m) cin >> C[i];
    vector<vector<ll>> dp(m + 1, vector<ll>(n + 1, INT64_MAX));
    dp[0][0] = 0;
    rep(i, m)
    {
        rep(j, n + 1)
        {
            if (dp[i][j] != INT64_MAX)
            {
                dp[i + 1][j] = min(dp[i + 1][j], dp[i][j]);
                if (j != n)
                {
                    dp[i + 1][j + 1] = min(dp[i + 1][j + 1], dp[i][j] + D[j] * C[i]);
                }
            }
        }
    }
    cout << dp[m][n] << endl;
    return 0;
}

43　パ研杯2019 D - パ研軍旗

問題はこちらです！
問題文↓

全行に色を上書きしていく
赤、青、白の色を塗っていき、1マス塗るのに1costかかる
もともと塗りたい色が塗っていた場合は塗らなくてもいい
各列の色が隣り合わないようにするとき、最小のコストを求めてください

DP[i][j]において
i:N行目のコスト
j:赤、青、白の三色のどれか(3)
として、DP[n][3]を作成します
returnOther関数さんを作っとくと便利だったりする
コードはこんな感じです！

#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (ll i = 0; i < (n); ++i)
#define rep1(i, n) for (ll i = 1; i < (n); ++i)
#define rrep(i, n) for (ll i = n; i > 0; --i)
#define bitrep(i, n) for (ll i = 0; i < (1 << n); ++i)
#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()
#define yesNo(b) ((b) ? "Yes" : "No")
using ll = long long;
using ull = unsigned long long;
using ld = long double;
string alphabet = "abcdefghijklmnopqrstuvwxyz";
string ALPHABET = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
const double pi = 3.141592653589793;
ll smallMOD = 998244353;
ll bigMOD = 1000000007;

vector<int> returnOther(int x)
{
    if (x == 0)
    {
        return {1, 2};
    }
    else if (x == 1)
    {
        return {0, 2};
    }
    else
    {
        return {0, 1};
    }
}

int main()
{
    int n;
    cin >> n;
    vector<string> M(5);
    rep(i, 5) cin >> M[i];
    vector<vector<ll>> dp(n, vector<ll>(3, INT64_MAX));
    int nonR = 0, nonB = 0, nonW = 0;
    rep(i, 5)
    {
        if (M[i][0] != 'R')
            nonR++;
        if (M[i][0] != 'B')
            nonB++;
        if (M[i][0] != 'W')
            nonW++;
    }
    dp[0][0] = nonR;
    dp[0][1] = nonB;
    dp[0][2] = nonW;
    rep(i, n - 1)
    {
        int nonR = 0, nonB = 0, nonW = 0;
        rep(j, 5)
        {
            if (M[j][i + 1] != 'R')
                nonR++;
            if (M[j][i + 1] != 'B')
                nonB++;
            if (M[j][i + 1] != 'W')
                nonW++;
        }
        vector<ll> nonRBW = {nonR, nonB, nonW};
        rep(j, 3)
        {
            auto x = returnOther(j);
            rep(k, 2)
            {
                dp[i + 1][x[k]] = min(dp[i + 1][x[k]], dp[i][j] + nonRBW[x[k]]);
            }
        }
    }
    cout << min({dp[n - 1][0], dp[n - 1][1], dp[n - 1][2]}) << endl;
    return 0;
}

44　AOJ 1167 - ポロック予想

問題はこちらです！
問題文↓

n(n+1)(n+2) ⁄ 6という式の自然数nにある数を代入して求まった答えを正四面体数という
正四面体数のいくつかを取り出して、入力で与えられる数を作成して、作ることのできる最小の個数を求めてください  
また、正四面体数の中でも奇数のものでも同じ操作を行ってください

はじめ、正四面体数のindexが奇数のものと読み間違えていて、悩みました、、、
10⁶未満の正四面体数は180個しか無いので、普通の重複有りナップザック問題
DP[n][180]を作ってナップザックする
コードはこんな感じです！

#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (ll i = 0; i < (n); ++i)
#define rep1(i, n) for (ll i = 1; i < (n); ++i)
#define rrep(i, n) for (ll i = n; i > 0; --i)
#define bitrep(i, n) for (ll i = 0; i < (1 << n); ++i)
#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()
#define yesNo(b) ((b) ? "Yes" : "No")
using ll = long long;
using ull = unsigned long long;
using ld = long double;
string alphabet = "abcdefghijklmnopqrstuvwxyz";
string ALPHABET = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
const double pi = 3.141592653589793;
ll smallMOD = 998244353;
ll bigMOD = 1000000007;

int main()
{
    ll x;
    cin >> x;
    vector<ll> items, oddItems;
    ll c = 1;
    while (c * (c + 1) * (c + 2) / 6 < 1e6)
    {
        items.push_back(c * (c + 1) * (c + 2) / 6);
        if (c * (c + 1) * (c + 2) / 6 % 2)
        {
            oddItems.push_back(c * (c + 1) * (c + 2) / 6);
        }
        c++;
    }
    vector<ll> dp(1e6, INT32_MAX), oddDp(1e6, INT32_MAX);
    dp[0] = 0;
    rep(i, items.size())
    {
        rep(j, 1e6)
        {
            if (j - items[i] >= 0)
            {
                dp[j] = min(dp[j], dp[j - items[i]] + 1ll);
            }
        }
    }
    oddDp[0] = 0;
    rep(i, oddItems.size())
    {
        rep(j, 1e6)
        {
            if (j - oddItems[i] >= 0)
            {
                oddDp[j] = min(oddDp[j], oddDp[j - oddItems[i]] + 1ll);
            }
        }
    }
    while (x != 0)
    {
        cout << dp[x] << " " << oddDp[x] << endl;
        cin >> x;
    }
    return 0;
}

AOJって意外とむずい

45　AOJ 2199 - 差分パルス符号変調

問題はこちらです！
問題文↓

ある数がn個とコードブック(数列)が与えられるので、y_0=128として、
y_i=y_(i-1)+C[x]で作られるy_iとある数のi番目の差の2乗の総和が最小になるような値を求めてください
ただし、y_iが0未満になる場合はy_i=0に、y_iが256以上になるときはy_i=255にまるめてください

結構難しいです、、、
N回の値のステートと、256個のステートを使うことで解けました
コードはこんな感じです

#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (ll i = 0; i < (n); ++i)
#define rep1(i, n) for (ll i = 1; i < (n); ++i)
#define rrep(i, n) for (ll i = n; i > 0; --i)
#define bitrep(i, n) for (ll i = 0; i < (1 << n); ++i)
#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()
#define yesNo(b) ((b) ? "Yes" : "No")
using ll = long long;
using ull = unsigned long long;
using ld = long double;
string alphabet = "abcdefghijklmnopqrstuvwxyz";
string ALPHABET = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
const double pi = 3.141592653589793;
ll smallMOD = 998244353;
ll bigMOD = 1000000007;

int main()
{
    ll n, m;
    cin >> n >> m;
    while (!(n == 0 && m == 0))
    {
        vector<ll> C(m), X(n);
        rep(i, m) cin >> C[i];
        rep(i, n) cin >> X[i];
        vector<vector<ll>> dp(20001, vector<ll>(256, INT32_MAX));
        dp[0][128] = 0;
        rep(i, n)
        {
            rep(j, 256)
            {
                if (dp[i][j] == INT32_MAX)
                    continue;
                rep(k, m)
                {
                    ll yn = j + C[k];
                    if (yn < 0)
                        yn = 0;
                    if (yn > 255)
                        yn = 255;
                    ll s = (X[i] - yn) * (X[i] - yn);
                    dp[i + 1][yn] = min(dp[i + 1][yn], dp[i][j] + s);
                }
            }
        }
        ll ans = INT32_MAX;
        rep(i, 256)
        {
            ans = min(ans, dp[n][i]);
        }
        cout << ans << endl;
        cin >> n >> m;
    }
    return 0;
}

DPﾁｮｯﾄﾜｶﾙようになったはず,,,

終わりに

最後まで見てくださりありがとうございました！
次は区間DPです！
ではまた

ルクの競プロ部屋

学生の競プロ生活を見たい人はどぞ

競プロ精選 100 問 by C++<動的計画法：ナップザック DP またはその亜種>

はじめに

39　JOI 2011 予選 4 - 1 年生

40　JOI 2012 予選 4 - パスタ

41　JOI 2013 予選 4 - 暑い日々

42　JOI 2015 予選 4 - シルクロード

43　パ研杯2019 D - パ研軍旗

44　AOJ 1167 - ポロック予想

45　AOJ 2199 - 差分パルス符号変調

終わりに

はじめに

39 JOI 2011 予選 4 - 1 年生

40 JOI 2012 予選 4 - パスタ

41 JOI 2013 予選 4 - 暑い日々

42 JOI 2015 予選 4 - シルクロード

43 パ研杯2019 D - パ研軍旗

44 AOJ 1167 - ポロック予想

45 AOJ 2199 - 差分パルス符号変調

終わりに

39　JOI 2011 予選 4 - 1 年生

40　JOI 2012 予選 4 - パスタ

41　JOI 2013 予選 4 - 暑い日々

42　JOI 2015 予選 4 - シルクロード

43　パ研杯2019 D - パ研軍旗

44　AOJ 1167 - ポロック予想

45　AOJ 2199 - 差分パルス符号変調