数字の書いてあるN枚のカードから、足してAになる組み合わせの数をかぞえる
C: 高橋君とカード / Tak and Cards - AtCoder Beginner Contest 044 | AtCoder
こちらのAtCoderの過去問が、自分には難しかったので、理解したのが吹っ飛ばないうちに備忘録として書きます。
模範解答
http://arc060.contest.atcoder.jp/data/arc/060/editorial.pdf
模範回答のコード
自分の理解
3.2 満点回答1です。
dp[j][k][s]=(x1,...,xj から k 枚選んで xi の合計を s にするような選び方の総数)
を求められればいいわけですが、この定義(以下)がよくわからなかった。
dp[j][k][s] =
⎧1 (j = 0, k = 0, s = 0 のとき)
⎨dp[j − 1][k][s] (j ≥ 1,s<xj のとき)
⎪dp[j − 1][k][s] + dp[j − 1][k − 1][s − xj ] (j ≥ 1, k ≥ 1, s ≥ xj のとき)
⎩0 (上記いずれでもないとき)
まず、
dp[j − 1][k][s] + dp[j − 1][k − 1][s − xj ] (j ≥ 1, k ≥ 1, s ≥ xj のとき)
これについて考える。
dp[j − 1][k][s]
は、xj
を選ばない時。選ばないので、[x1,...,x(j-1)]
からk
枚選んで合計がs
になるものを求める。
dp[j − 1][k − 1][s − xj ]
は、xj
を選んだ時。選んだので、[x1,...,x(j-1)]
からk
枚選んで合計がs - xj
になるものを求める。
次に、
dp[j − 1][k][s] (j ≥ 1,s<xj のとき)
これは、s < xj
つまり合計s
よりxj
が大きい場合で、xj
を選ぶパターンがない。
ここまで理解するのに時間がかかった...