ABC-044-C 高橋君とカード

■■■問題■■■

高橋君は、N枚のカードを持っています。
i(1 <= i <= N)番目のカードには、整数xiが書かれています。

高橋君は、これらのカードの中から1枚以上を選び、
選んだカードに書かれた整数の平均をちょうどAにしたいと考えています。

そのようなカードの選び方が何通りあるか求めてください。

■■■入力■■■

N A
x1 x2 ・・・ xN

●1 <=  N <= 50
●1 <=  A <= 50
●1 <= xi <= 50
●N,A,xi はいずれも整数である

■■■出力■■■

書かれた整数の平均がちょうどAとなるようなカードの選び方の総数を出力せよ。

C#のソース

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static string InputPattern = "InputX";

    static List<string> GetInputList()
    {
        var WillReturn = new List<string>();

        if (InputPattern == "Input1") {
            WillReturn.Add("4 8");
            WillReturn.Add("7 9 8 9");
            //5
            //平均が8となるカードの選び方は、以下の5通りです。
            //●3枚目のカードのみを選ぶ。
            //●1枚目と2枚目のカードを選ぶ。
            //●1枚目と4枚目のカードを選ぶ。
            //●1枚目、2枚目および3枚目のカードを選ぶ。
            //●1枚目、3枚目および4枚目のカードを選ぶ。
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("3 8");
            WillReturn.Add("6 6 9");
            //0
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("8 5");
            WillReturn.Add("3 6 2 8 7 6 5 9");
            //19
        }
        else if (InputPattern == "Input4") {
            WillReturn.Add("33 3");
            var sb = new System.Text.StringBuilder();
            for (int I = 1; I <= 33; I++) {
                if (I >= 2) sb.Append(" ");
                sb.Append(3);
            }
            WillReturn.Add(sb.ToString());
            //8589934591
            //答えは32ビット整数型に収まらない場合があります
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static void Main()
    {
        List<string> InputList = GetInputList();
        int[] wkArr = InputList[0].Split(' ').Select(X => int.Parse(X)).ToArray();
        int A = wkArr[1];
        int[] XArr = InputList[1].Split(' ').Select(X => int.Parse(X)).ToArray();

        //場合の数[枚数,合計]なDP表
        int UB_I = wkArr[0];
        int UB_J = XArr.Sum();
        long[,] DPArr = new long[UB_I + 1, UB_J + 1];
        DPArr[0, 0] = 1;

        foreach (int EachX in XArr) {
            for (int I = UB_I; 0 <= I; I--) {
                for (int J = UB_J; J >= 0; J--) {
                    if (DPArr[I, J] == 0) continue;
                    int NewI = I + 1;
                    int NewJ = J + EachX;
                    DPArr[NewI, NewJ] += DPArr[I, J];
                }
            }
        }

        long AnswerCnt = 0;
        for (int I = 1; I <= UB_I; I++) {
            for (int J = 0; J <= UB_J; J++) {
                if (J == A * I)
                    AnswerCnt += DPArr[I, J];
            }
        }
        Console.WriteLine(AnswerCnt);
    }
}

解説

配るDPで、場合の数[枚数,合計]を更新してます。