ABC318-E Sandwiches

問題へのリンク

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

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

        // PosList[値]なDict
        var PosListDict = new Dictionary<int, List<int>>();
        for (int I = 0; I <= AArr.GetUpperBound(0); I++) {
            if (PosListDict.ContainsKey(AArr[I]) == false) {
                PosListDict[AArr[I]] = new List<int>();
            }
            PosListDict[AArr[I]].Add(I);
        }

        long Answer = 0;
        foreach (var EachPair in PosListDict) {
            long CurrAnswer = 0;

            List<int> CurrList = EachPair.Value;

            int LastInd = CurrList.Count - 1;
            for (int I = 0; I <= LastInd - 1; I++) {
                int CurrPos = CurrList[I];
                int NextPos = CurrList[I + 1];

                long SpaceRange = NextPos - CurrPos - 1;

                long LeftCnt = I + 1;
                long RightCnt = LastInd - I;

                CurrAnswer += SpaceRange * LeftCnt * RightCnt;
            }
            Answer += CurrAnswer;
        }
        Console.WriteLine(Answer);
    }
}

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>();
        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();

        long MaxVal = AArr.Max();

        // 全体の件数[値]な配列
        long[] EntireCntArr = new long[MaxVal + 1];

        // 左の件数[値]な配列
        long[] LeftCntArr = new long[MaxVal + 1];

        // 左の件数 * 右の件数 [値]な配列
        long[] ProdArr = new long[MaxVal + 1];

        long ProdSum = 0;

        foreach (long EachA in AArr) {
            EntireCntArr[EachA]++;
        }

        long Answer = 0;
        foreach (long EachA in AArr) {
            // 解に計上
            Answer += ProdSum - ProdArr[EachA];

            // 左に移動
            LeftCntArr[EachA]++;

            // 再計算
            ProdSum -= ProdArr[EachA];
            long LeftCnt = LeftCntArr[EachA];
            ProdArr[EachA] = LeftCnt * (EntireCntArr[EachA] - LeftCnt);
            ProdSum += ProdArr[EachA];
        }
        Console.WriteLine(Answer);
    }
}

解説

両端の値ごとに考える方法で、
1と両端にするとした場合に
12122122211122221
のような、1が連続してるケースに気をつける必要があります。