ツバサの備忘録

主に備忘録代わりに精進記録を載せていくつもりです。

ABC044 C - 高橋君とカード / Tak and Cards

問題
提出コード
CはDPのCですね!

解法

動的計画法を利用します。
dp[i][j][k] = 数列のi番目までのうち、j個の要素を足した結果がkになるようなものの個数
とします。
すると、
dp[i][j][k] = dp[i-1][j][k] + dp[i-1][j-1][k-x_i]
右辺の左の項は、x_iを使用しないパターン(1つ前の個数がそのまま引き継がれます)、右の項は、x_iを使用したパターン(使用すると、jが1つ増えるので、見るべき場所は1つ前になります)です。
答えがどこにあるかというと、平均がAになるので、j個数列の要素を選んでいるときは、和がj×Aになっていなければなりません。よって、
dp[n][j][j×A]
の和を求めれば、答えになります。