AtCoder dp例題といてみた4

AtCoder dp例題といてみた

今回の問題

問題文

高橋君はレベル $N$ の赤い宝石を $1$ 個持っています。(他に宝石は持っていません。)
高橋君は次の操作を好きなだけ行うことができます。

• レベル $n$ の赤い宝石 ($n$ は $2$ 以上) を「レベル $n-1$ の赤い宝石 $1$ 個と、レベル $n$ の青い宝石 $X$ 個」に変換する。
• レベル $n$ の青い宝石 ($n$ は $2$ 以上) を「レベル $n-1$ の赤い宝石 $1$ 個と、レベル $n-1$ の青い宝石 $Y$ 個」に変換する。

高橋君はレベル $1$ の青い宝石ができるだけたくさんほしいです。操作によって高橋君はレベル $1$ の青い宝石を最大何個入手できますか？

制約

• $1 \leq N \leq 10$
• $1 \leq X \leq 5$
• $1 \leq Y \leq 5$
• 入力される値はすべて整数

自分の回答

#include <bits/stdc++.h>
using namespace std;

int main() {
    int N;
    long long X, Y;
    cin >> N >> X >> Y;

    // レベル i の 赤(r) と 青(b) から得られるレベル1青宝石の数
    vector<long long> r(N + 1), b(N + 1);

    // 初期状態 (レベル1)
    r[1] = 0;
    b[1] = 1;

    // レベル2からNまで順番に計算 (DP)
    for (int i = 2; i <= N; i++) {
        // 青い宝石の計算: 赤(i-1) 1個 + 青(i-1) Y個
        b[i] = r[i-1] + Y * b[i-1];

        // 赤い宝石の計算: 赤(i-1) 1個 + 青(i) X個
        // ※先に計算した b[i] を使う点に注意
        r[i] = r[i-1] + X * b[i];
    }

    // 求めたいのは「レベルNの赤い宝石」から得られる数
    cout << r[N] << endl;

    return 0;
}

自分なりの解説

$$B[n] = R[n-1] + Y \times B[n-1]$$
$$R[n] = R[n-1] + X \times B[n]$$
という漸化式がかけるのでこれをRがNになるまで計算していくと解くことができる。

dpを勉強して

dpはとても難しい印象が強くてなかなか手がつかなかったが、どうやってその発想になるの？！みたいな問題は多くあったが実装は比較的楽だった。たくさん問題数をこなして、コンテスト中にも解けるようになっていきたい。