ABC439-D Kadomatsu Subsequence

問題へのリンク

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("10");
            WillReturn.Add("3 10 7 10 7 6 7 6 5 14");
            //7
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("6");
            WillReturn.Add("210 210 210 210 210 210");
            //0
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("21");
            WillReturn.Add("49 30 50 21 35 15 21 70 35 9 50 70 21 49 30 50 70 15 9 21 30");
            //34
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static long[] GetSplitArr(string pStr)
    {
        return (pStr == "" ? new string[0] : pStr.Split(' ')).Select(pX => long.Parse(pX)).ToArray();
    }

    static void Main()
    {
        List<string> InputList = GetInputList();
        long[] AArr = GetSplitArr(InputList[1]);

        long AnswerSei = Solve(AArr);

        Array.Reverse(AArr);
        long AnswerRev = Solve(AArr);

        Console.WriteLine(AnswerSei + AnswerRev);
    }

    static long Solve(long[] pAArr)
    {
        var Prod5CntDict = new Dictionary<long, long>();

        long Answer = 0;
        foreach (long EachA in pAArr) {
            long Prod3 = EachA * 3;
            long Prod5 = EachA * 5;
            long Prod7 = EachA * 7;

            if (Prod5CntDict.ContainsKey(Prod5) == false) {
                Prod5CntDict[Prod5] = 0;
            }
            Prod5CntDict[Prod5]++;

            long Cnt1 = 0;
            if (Prod5CntDict.ContainsKey(Prod7)) {
                Cnt1 = Prod5CntDict[Prod7];
            }
            long Cnt2 = 0;
            if (Prod5CntDict.ContainsKey(Prod3)) {
                Cnt2 = Prod5CntDict[Prod3];
            }
            Answer += Cnt1 * Cnt2;
        }
        return Answer;
    }
}

解説

まず受験算数の連比の知識を使って整理します。

A : B : C = 3 : 5: 7
から
A : B = 3 : 5 ⇔ 3B = 5A
B : C = 5 : 7 ⇔ 5C = 7B
を導出できます。

なので、配列の正順と逆順で、
配列値を5倍した値の度数分布表を持ちながら
積の法則を使って、解の数を求めれば良いです。