ABC206-C Swappable

問題へのリンク

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");
            WillReturn.Add("1 7 1");
            //2
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("10");
            WillReturn.Add("1 10 100 1000 10000 100000 1000000 10000000 100000000 1000000000");
            //45
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("20");
            WillReturn.Add("7 8 1 1 4 9 9 6 8 2 4 1 1 9 5 5 5 3 6 4");
            //173
        }
        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 = new Dictionary<long, long>();
        foreach (long EachLong in AArr) {
            if (CntDict.ContainsKey(EachLong) == false) {
                CntDict[EachLong] = 0;
            }
            CntDict[EachLong]++;
        }

        long[] ValuesArr = CntDict.Values.ToArray();

        long Answer = 0;
        long ValuesSum = ValuesArr.Sum();
        foreach (long EachValue in ValuesArr) {
            ValuesSum -= EachValue;
            Answer += EachValue * ValuesSum;
        }
        Console.WriteLine(Answer);
    }
}

解説

9 9 9 8 8 7 7 7 7 6
という数列で考えると
それぞれの件数は
3 2 4 1
なので
4C2通りの選択方法の、それぞれの積の総和が解になります。

ナイーブに計算するとTLEになるので
 3 * (2+4+1)
+2 * (4+1)
+4 * 1
のように結合法則を使って、計算量を落とす必要があります。