Kazun の競プロ記録

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

AtCoder Beginner Contest 281 D問題 Max Multiple

AtCoder ABC281 ABC D問題 400 pts

問題

提出解答

問題の概要

$N$ 個の整数 $A_1, \dots, A_N$ から $K$ 個の整数を選び出す方法のうち, その $K$ 個の総和が $D$ の倍数になる取り出し方は存在するか? 存在するならば $D$ の倍数になるような取り出し方のうち, その総和の最大値を求めよ.

制約

$1 \leq K \leq N \leq 100$
$1 \leq D \leq 100$
$0 \leq A_i \leq 10^9$

解法

動的計画法で解くことにする. $0 \leq i \leq N, 0 \leq j \leq K, 0 \leq r \lt D$ に対して, ${\rm DP}[i,j,r]$ を以下で定義する.

$A_1, \dots, A_i$ から $j$ 個選び出す方法のうち, $D$ で割った余りが $r$ であるような選び方のうち, その総和の最大値 (存在しないならば $-\infty$ ).

自明なケースは $i=0$ のときで,

${\rm DP}[i,j,r]=\begin{cases} 0 & (j=0, r=0) \\ -\infty & ({\rm otherwise}) \end{cases}$

である.

更新については $A_i$ を選択するか, しないかで場合分けすることによって,

${\rm DP}[i,j,r]=\max({\rm DP}[i-1, j, k], {\rm DP}[i-1, j-1, (r-A_i)~({\rm mod} D) ] +A_i)$

となる.

これによる最終解答は ${\rm DP}[N,K,0]$ である. 計算量は $O(NKD)$ 時間である.