DPL_4_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("3 14");
            WillReturn.Add("3 1 2");
            WillReturn.Add("4 8 2");
            WillReturn.Add("1 2 3");
            WillReturn.Add("7 3 2");
            //9
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("5 4");
            WillReturn.Add("1 1 1 1 1");
            WillReturn.Add("1 1 1 1 1");
            WillReturn.Add("1 1 1 1 1");
            WillReturn.Add("1 1 1 1 1");
            //625
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static void Main()
    {
        List<string> InputList = GetInputList();
        long[] wkArr = InputList[0].Split(' ').Select(pX => long.Parse(pX)).ToArray();
        long V = wkArr[1];

        long[] AArr = InputList[1].Split(' ').Select(pX => long.Parse(pX)).ToArray();
        long[] BArr = InputList[2].Split(' ').Select(pX => long.Parse(pX)).ToArray();
        long[] CArr = InputList[3].Split(' ').Select(pX => long.Parse(pX)).ToArray();
        long[] DArr = InputList[4].Split(' ').Select(pX => long.Parse(pX)).ToArray();

        Dictionary<long, long> CntDict1 = DeriveCntDict(AArr, BArr);
        Dictionary<long, long> CntDict2 = DeriveCntDict(CArr, DArr);

        long Answer = 0;
        foreach (var EachPair in CntDict1) {
            long RestVal = V - EachPair.Key;
            if (CntDict2.ContainsKey(RestVal)) {
                Answer += EachPair.Value * CntDict2[RestVal];
            }
        }
        Console.WriteLine(Answer);
    }

    // 配列2つを引数として、場合の数[和]を返す
    static Dictionary<long, long> DeriveCntDict(long[] pArr1, long[] pArr2)
    {
        var CntDict = new Dictionary<long, long>();
        long UB = pArr1.GetUpperBound(0);
        for (long I = 0; I <= UB; I++) {
            for (long J = 0; J <= UB; J++) {
                long SumVal = pArr1[I] + pArr2[J];
                if (CntDict.ContainsKey(SumVal) == false) {
                    CntDict[SumVal] = 0;
                }
                CntDict[SumVal]++;
            }
        }
        return CntDict;
    }
}

解説

場合の数[和]
を求めてから、積の法則を使ってます。