Kazun の競プロ記録

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

AtCoder Beginner Contest 286 D問題 Money in Hand

AtCoder ABC286 ABC D問題 400 pts

問題
提出解答
問題の概要
- 制約
解法

問題

提出解答

問題の概要

$N$ 種類の硬貨を持っており, $i$ 種類目の硬貨は $A_i$ 円であり, $B_i$ 枚持っている.

これらから何枚かの硬貨を用いることにより, ちょうど $X$ 円を支払うことができるか?

制約

$1 \leq N \leq 50$
$1 \leq X \leq 10^4$
$1 \leq A_i \leq 100$
$1 \leq B_i \leq 50$
$A_1, \dots, A_N$ は全て異なる.

解法

次のような問題を解ければ十分である.

$M$ 枚の硬貨がある. $i$ 枚目の硬貨は $S_i$ 円である (重複が含まれる可能性がある). このとき, これらの硬貨を何枚か用いて, ちょうど $Y$ 円を支払うことは可能か?

この問題を動的計画法で解くことにする. $0 \leq i \leq M, 0 \leq j \leq Y$ に対して, ${\rm DP}[i,j$ ] を以下で定義する.

$i$ 枚目までの硬貨を用いることによって, ちょうど $j$ 円支払うことが可能ならば, $\mathbb{T}$ , 不可能ならば, $\mathbb{F}$ とする.

ベースケースは $i=0$ のときで,

${\rm DP}[0,j]=\begin{cases} \mathbb{T} & (i=0) \\ \mathbb{F} & (i \neq 0) \end{cases}$

である.

更新式について, $i$ 枚目の硬貨を使うか使わないかで場合分けをすることにより, 次のような更新式を導くことができる.

${\rm DP}[i,j]=\begin{cases} {\rm DP}[i-1, j] & (j \lt S_i) \\ {\rm DP}[i-1, j] \lor {\rm DP}[i-1, j-S_i] & (j \geq S_i) \end{cases}$

この動的計画法により, ${\rm DP}[M, Y]$ が答えになる. 時間計算量は $O(MY)$ 時間である.

元問題を次のようにして上の問題に帰着させる.

$M=B_1+\dots+B_N$
次のようにしてを設定する.
- $S_1, S_2, \dots, S_{B_1}$ を $A_1$ にする.
- $S_{B_1+1}, S_{B_1+2}, \dots, S_{B_1+B_2}$ を $A_2$ にする.
- $\vdots$
$Y=X$

このようにして上の問題に帰着させることによって, $\displaystyle O \left(\left( \sum_{i=1}^N B_i \right) X \right)$ 時間で解くことができる.