Kazun の競プロ記録

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

AtCoder Beginner Contest 248 C問題 Dice Sum

AtCoder ABC ABC248 C問題 300 pts

問題

提出解答

問題の概要

以下を満たす長さ $N$ の整数列 $A=(A_i)$ の個数を求めよ.

$1 \leq A_i \leq M$
$\displaystyle \sum_{i=1}^N A_i \leq K$

制約

$1 \leq N \leq 50$
$1 \leq M \leq 50$
$N \leq K \leq NM$

解法

動的計画法で解く. ${\rm DP}[i,x]$ で, 先頭 $i$ 項まで決定し, 和が $x$ になるような整数列の個数とする.

ベースケースは ${\rm DP}[0,x]=[x=0 ]$ である.

更新式は, 第 $i$ 項で分割することにすると,

${\rm DP}[i,x\]=\sum\_{a=1}\^M {\rm DP}[i-1, x-a\]$

である.

この動的計画法において, 答えは ${\rm DP}[N, K]$ である. なお, 動的計画法の配列については各項が正であるため, $0 leq x \leq K$ の範囲で十分である.

時間計算量は要素数が $O(NK)$ ,更新式が1要素あたり $O(M)$ であるので, 全体で $O(NMK)$ となる.