Kazun の競プロ記録

競技プログラミングに関する様々な話題を執筆します.

AtCoder Beginner Contest 260 C問題 Changing Jewels

AtCoder ABC ABC260 C問題 300 pts

問題

提出解答

問題の概要

レベル $N$ の赤い宝石を1個持っている. 次の操作を任意回繰り返す.

レベル $n~(n \geq 2)$ の赤い宝石1個をレベル $(n-1)$ の赤い宝石1個とレベル $n$ の青い宝石 $X$ 個に変換する.
レベル $n~(n \geq 2)$ の赤い宝石1個をレベル $(n-1)$ の赤い宝石1個とレベル $(n-1)$ の青い宝石 $Y$ 個に変換する.

制約

$1 \leq N \leq 10$
$1 \leq X,Y \leq 5$

解法

$n=1,2, \dots, N$ に対して, $R_n, B_n$ をそれぞれ,

$R_n$ : レベル $n$ の赤い宝石を1個だけ持っている状態から初めた場合の最終的なレベル $1$ の青い宝石の個数.
$B_n$ : レベル $n$ の青い宝石を1個だけ持っている状態から初めた場合の最終的なレベル $1$ の青い宝石の個数.

とする. すると, 漸化式として,

$R_n=R_{n-1}+X B_n, \quad B_n=R_{n-1}+Y B_{n-1}$

が立ち, 初期条件 $R_1=0, B_1=1$ と合わせることにより, $R_N$ が答えになる.

この漸化式を解く方法としては $N \leq 10$ であることから, 動的計画法または再帰で解くことができる.