C - Changing Jewels Editorial by Nyaan
この問題は 再帰関数 ・ 動的計画法 のいずれかを用いると解くことができる問題です。
再帰関数・メモ化再帰・動的計画法に関しては以前に ABC247-C の解説 でも説明したので、再帰関数や動的計画法を知らない人はそちらの問題を解いて解説を読んでみるとよいでしょう。
1.動的計画法
解法の 1 つは動的計画法(通称 DP) です。
\(r_1, r_2, \dots, r_N\) および \(b_1, b_2, \dots, b_N\) を次のように定義します。
- \(r_i\) : レベル \(i\) の赤い宝石を \(1\) 個持っている状態からはじめて、入手できるレベル \(1\) の青い宝石の個数
- \(b_i\) : レベル \(i\) の青い宝石を \(1\) 個持っている状態からはじめて、入手できるレベル \(1\) の青い宝石の個数
まず、\(r_1, b_1\) は次のように定まります。
- レベル \(1\) の赤い宝石からレベル \(1\) の青い宝石は得られない。よって \(r_1 = 0\) である。
- レベル \(i\) の青い宝石 \(1\) 個からレベル \(1\) の青い宝石は(少し奇妙な表現になるが)ちょうど \(1\) 個得られる。 よって \(b_1 =1\) である。
次に、\(r_i,b_i\) \((i \geq 2)\) は問題文の定義から次の式で表せます。
\[ \begin{aligned} b_n &= r_{n-1} + b_{n-1} \times Y\\ r_n &= r_{n-1} + b_{n} \times X\\ \end{aligned} \]
よって、上の式に従って \(r_n, b_n\) を \(n=1\) から \(n=N\) の順に計算していけばよいです。
- 注意すべき点として、\(r_n\) より先に \(b_n\) を計算する必要がある点があります。なぜならば、\(r_n\) を求めるのに \(b_n\) の値が必要だからです。
実装は以下の通りです。
#include <iostream>
using namespace std;
long long N, X, Y, r[12], b[12];
int main() {
cin >> N >> X >> Y;
r[1] = 0, b[1] = 1;
for (int n = 2; n <= N; n++) {
b[n] = r[n - 1] + b[n - 1] * Y;
r[n] = r[n - 1] + b[n] * X;
}
cout << r[N] << "\n";
}
2. 再帰関数
もう一つの解法は再帰関数を用いる解法です。
再帰とは、ある物事を説明するときに、それ自身が説明の中に入っていることを言います。1. の解法を見るとわかる通り、ある宝石から得られるレベル \(1\) の青い宝石の個数は他のある宝石から得られるレベル \(1\) の青い宝石の個数によって定まるものであり、再帰的な関係にあると言えます。
再帰関数とは、関数の内部で自分自身を呼び出す関数のことを言います。上に説明したような再帰的な構造は、再帰関数を用いるとそのまま実装することができます。
具体的には、1. の解法と同様の式を再帰関数の形で実装すればよいです。実装は以下の通りです。
#include <iostream>
using namespace std;
int N, X, Y;
long long calc(int level, bool is_red) {
if (level == 1) return is_red ? 0 : 1;
if (is_red) {
return calc(level - 1, true) + calc(level, false) * X;
} else {
return calc(level - 1, true) + calc(level - 1, false) * Y;
}
}
int main() {
cin >> N >> X >> Y;
cout << calc(N, true) << endl;
}
- これは余談ですが、赤い宝石と青い宝石で別々の再帰関数を使おうとすると 相互再帰 と呼ばれる状態になって、言語によっては実装が複雑になります。(例えば C++ ではプロトタイプ宣言が必要になります。)初心者の方は上の実装のように 1 つの関数で再帰するようにした方が簡明でしょう。
posted:
last update: