ABC159-D Banned K

問題へのリンク

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

    static void Main()
    {
        List<string> InputList = GetInputList();

        long[] AArr = InputList[1].Split(' ').Select(pX => long.Parse(pX)).ToArray();

        // 数値ごとの件数を求める
        var CntDict = AArr.GroupBy(pX => pX).ToDictionary(pX => pX.Key, pX => pX.Count());

        long PatternSum = 0;
        foreach (var EachPair in CntDict) {
            if (EachPair.Value >= 2) {
                PatternSum += DeriveCombi(EachPair.Value, 2);
            }
        }

        for (int I = 0; I <= AArr.GetUpperBound(0); I++) {
            long MinusPatternCnt = CntDict[AArr[I]] - 1;
            Console.WriteLine(PatternSum - MinusPatternCnt);
        }
    }

    //nCrを求める
    static long DeriveCombi(long pN, long pR)
    {
        long WillReturn = 1;
        pR = Math.Min(pR, pN - pR);

        var DivList = new List<long>();
        for (long I = 2; I <= pR; I++) {
            DivList.Add(I);
        }

        for (long I = pN - pR + 1; I <= pN; I++) {
            WillReturn *= I;

            for (int J = DivList.Count - 1; 0 <= J; J--) {
                if (WillReturn % DivList[J] == 0) {
                    WillReturn /= DivList[J];
                    DivList.RemoveAt(J);
                }
            }
        }
        return WillReturn;
    }
}

解説

最初に、同じ色を2つ取る場合の数を求めます。
次に、それぞれのボールをBanするので、
Banするボールを必ず選択して、同じ色を2つ取る場合の数を求め、
引き算してます。