Kazun の競プロ記録

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

AtCoder Beginner Contest 271 D問題 Flip and Adjust

AtCoder ABC271 ABC D問題 400 pts

問題

提出解答

問題の概要

$N$ 枚のカードがある. $i$ 番目のカードの表には整数 $A_i$ , 裏には $B_i$ が書かれている.

各カードは表か裏のうちのどちらか一方を上にして置くことができる.

上に向けられた面に書かれている $N$ 個の整数の総和をちょうど $S$ にすることは可能か? 可能ならば各カードの表裏の一例を挙げよ.

制約

$1 \leq N \leq 100$
$1 \leq S \leq 10000$
$1 \leq A_i, B_i \leq 100$

解法

次のような動的計画法で解くことにする. $0 \leq i \leq N, 0 \leq j \leq S$ に対して, ${\rm DP}[i, j ]$ を

$i$ 枚のカード $1,2, \dots, i$ までのカードの表裏を決めた場合において, 総和を $j$ にすることが可能ならば $\mathbb{T}$ , 不可能ならば $\mathbb{F}$ .

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

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

である.

更新式については $i$ 枚目を表にするか裏にするかで場合分けすることによって,

${\rm DP}[i, j ]={\rm DP}[i-1, j-A_i ] \lor {\rm DP}[i-1, j-B_i ]$

となることもわかる. なお, $j \lt 0$ については ${\rm DP}[i, j ]=\mathbb{F}$ とする.

これにより, 総和を $S$ にすることが可能であることの必要十分条件は ${\rm DP}[N, S] =\mathbb{T}$ である.

また, 表裏の一例を挙げる場合についても, $1 \leq i \leq N, 0 \leq j \leq S$ について, 以下は同値である.

カード $1,2, \dots, i$ の表裏を決めた時, カード $i$ が表で総和が $j$ になる $i$ 枚の表裏が存在する.
${\rm DP}[i,j] =\mathbb{T}$ かつ ${\rm DP}[i-1,j-A_i ] =\mathbb{T}$

カード $i$ が裏で総和が $j$ になる $i$ 枚の表裏が存在する場合も同様である. これを利用することによってカード $N, (N-1), \dots, 1$ の順に表裏を決定できる.

よって, 動的計画法により計算量 $O(NS)$ 時間で求めることができた.