とある地味なブログ

プログラミングとお絵かきに関する雑記。

数字の書いてある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を選ぶパターンがない。

ここまで理解するのに時間がかかった...