Kazun の競プロ記録

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

AtCoder Beginner Contest 240 C問題 Jumping Takahashi

AtCoder ABC ABC240 C問題 300 pts

問題

提出解答

問題の概要

以下を満たす列 $S=(S_i)_{i=1}^N$ は存在するか?

$S_i \in \{a_i, b_i\} \quad (i=1,2, \dots, N)$
$\displaystyle \sum_{i=1}^N S_i=X$

制約

$1 \leq N \leq 100$
$1 \leq a_i \lt b_i \leq 100$
$1 \leq X \leq 10000$

解法

この問題はある意味での部分和問題である. そして, $N,X$ がそれほど大きくはないので, 今回は動的計画法で解くことにする.

${\rm DP}[i,x]$ で $S_1, \dots, S_i$ まで決めたとき, 和を $x$ にすることができるか? を表すとする (できるならば $\mathbb{T}$ , できないならば $\mathbb{F}$ ).

ベースケースは $i=0$ の場合で,

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

である.

更新式を考える. $S_i$ として $a_i$ を選んだ場合は $S_1, \dots, S_{i-1}$ において和を $x-a_i$ にできるか? という問題に帰着される. これは ${\rm DP}[i-1, x-a_i ]$ で既に計算されている. $S_i$ として $b_i$ を選んだ場合も考えることにより,

${\rm DP}[i,x]={\rm DP}[i-1, x-a_i] \lor {\rm DP}[i-1, x-b_i]$

となる.

この動的計画法によって, ${\rm DP}[N,X]$ が答えになる.

ここで, ${\rm DP}[i,x]$ において, $x \lt 0$ の場合は明らかに $\mathbb{F}$ である. また, $0 \leq a_i, b_i$ であるから, $x \gt X$ における情報は不要である. よって, $0 \leq i \leq N, 0 \leq x \leq X$ の場合においてのみ見れば良い. このことから, 時間計算量, 空間計算量ともに $O(NX)$ で求めることができる.