Kazun の競プロ記録

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

AtCoder Beginner Contest 275 F問題 Erase Subarrays

AtCoder ABC275 ABC F問題 500 pts

問題

提出解答

問題の概要

長さ $N$ の整数列 $A=(A_1, \dots, A_N)$ が与えられる.

$x=1,2, \dots, M$ に対して, 次の問題を解け.

$A$ から連続部分列を選び, その部分を削除することを $0$ 回以上行い, 残った整数列における整数の総和を $x$ にすることは可能か? 可能ならば操作回数の最小値を求めよ.

制約

$1 \leq N,M \leq 3000$
$1 \leq A_i \leq 3000$

解法

連続部分列を削除する代わりに, $0$ に置き換えるとしても答えは変わらない. 以降ではこのようにする.

次のような動的計画法を考える. ${\rm DP}[i,x,f]$ を

第 $i$ 項目まで見たとき, $i$ 項目を $0$ に ( $f$ : $T$ : する/ $F$ : しない) 場合における操作の最小値 (存在しない場合は $+\infty$ ).

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

${\rm DP}[0,x,f]=\begin{cases} 0 & (x=0, f=F) \\ +\infty & ({\rm otherwise}) \end{cases}$

である. 更新式について, 上のようにベースケースを定めたので, $(i-1)$ 項目が $F$ , $i$ 項目が $T$ の場合に新たな操作が必要になることに着目すると,

${\rm DP}[i,x,T]=\min ({\rm DP}[i-1,x,F ]+1, {\rm DP}[i-1,x,T ])$
${\rm DP}[i,x,F]=\min ({\rm DP}[i-1,x-A_i, F ], {\rm DP}[i-1, x-A_i, T])$

である.

$x=1,2, \dots, M$ に対して, $\displaystyle \min ({\rm DP}[N,x,T], {\rm DP}[N,x,F] )$ を答えれば良い.

計算量は $O(NM)$ 時間である.