ABC166-E This Message Will Self-Destruct in 5s

問題へのリンク

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("6");
            WillReturn.Add("2 3 3 1 3 1");
            //3
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("6");
            WillReturn.Add("5 2 4 2 8 8");
            //0
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("32");
            WillReturn.Add("3 1 4 1 5 9 2 6 5 3 5 8 9 7 9 3 2 3 8 4 6 2 6 4 3 3 8 3 2 7 9 5");
            //22
        }
        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();
        long UB = AArr.GetUpperBound(0);

        var DosuuDict = new Dictionary<long, long>();
        for (long J = 0; J <= UB; J++) {
            long CurrVal2 = (J + 1) - AArr[J];
            IncrementCnt(DosuuDict, CurrVal2);
        }

        long Answer = 0;
        for (long I = 0; I <= UB; I++) {
            long CurrVal1 = (I + 1) + AArr[I];
            long CurrVal2 = (I + 1) - AArr[I];
            DecrementCnt(DosuuDict, CurrVal2);

            if (DosuuDict.ContainsKey(CurrVal1)) {
                Answer += DosuuDict[CurrVal1];
            }
        }
        Console.WriteLine(Answer);
    }

    static void IncrementCnt(Dictionary<long, long> pDict, long pKey)
    {
        if (pDict.ContainsKey(pKey) == false) {
            pDict[pKey] = 0;
        }
        pDict[pKey]++;
    }

    static void DecrementCnt(Dictionary<long, long> pDict, long pKey)
    {
        pDict[pKey]--;
        if (pDict[pKey] == 0) {
            pDict.Remove(pKey);
        }
    }
}

解説

2つの添字のペアをIとJとし、
I < J とすると、

J - I = A[J] + A[I]
を満たせばよいと分かります。
移項すると
 I + A[I] = J - A[J]
になるので、
J - A[J]の度数分布表を更新しながら、
Iを左から全探索すればいいと分かります。