200AC - ABC044C: Tak and Cards - back-of-the-envelope

ABC044-C (300 points)

問題

数字が書かれた $N$ 枚のカードの中から $1$ 枚以上選び, 選んだカードに書かれた整数の平均を $A$ にする選び方の総数を求める.

$1 \leq N \leq 50$
$1 \leq A \leq 50$
$1 \leq x_i \leq 50$
入力は全て整数

方針

与えられたカードから $1$ 枚以上選んで作ることのできる和を素直に全て求める.
collections.Counterをうまく使う.
$x_1, \ldots, x_i$ のカードで作ることのできる和の集合を $S_i$ とすると, $x_1, \ldots, x_i, x_{i + 1}$ のカードで作ることのできる和の集合は
$S_{i + 1} = \{ s, x_{i + 1}, s + x_{i + 1} | s \in S_i \}$

import collections

# input
n, a = map(int, input().split())
X = [int(i) - a for i in input().split()]

S = collections.Counter([0, X[0]])
# Xから1枚以上選んで作ることが可能な和:作り方の場合の数
# 初期状態はX = X[0]のときに作ることが可能な和
# 1枚も選ばない＝0:1通り
# X[0]のみ選ぶ＝X[0]:1通り

for i in X[1:]: # 選べるカードを増やしていく (X[0] ~ X[i] から選ぶ)
    S_temp = collections.Counter()
    for s, c in S.items():
        S_temp[s + i] += c # X[0] ~ X[i - 1] で作れる和に X[i] を足す
    S += S_temp

print(S[0] - 1) # 1枚も選ばないのはルール違反