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

    static int[] mAArr;
    static int UB;

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

        long Answer = 0;
        for (int I = 0; I <= UB; I++) {
            int MinInd;
            bool Result = ExecDP(I, out MinInd);

            //Console.WriteLine("I={0}での結果={1},MinInd={2}", I, Result, MinInd);

            if (Result) {
                Answer += UB - MinInd + 1;
            }
        }
        Console.WriteLine(Answer);
    }

    // 開始添字を引数として、DPを行い、等差数列ができる最小添字を設定
    static bool ExecDP(int pStaInd, out int pMinInd)
    {
        pMinInd = -1;

        // 状態のHashSetなDP表
        var PrevSet = new HashSet<int>();

        for (int I = pStaInd; I <= UB; I++) {
            var CurrSet = new HashSet<int>();

            int CurrHash = GetHash(mAArr[I], 0);
            CurrSet.Add(CurrHash);

            foreach (int EachHash in PrevSet) {
                int Val1, Val2;
                SetVal(EachHash, out Val1, out Val2);

                if (Val2 == 0) {
                    Val2 = mAArr[I];
                    int NewHash = GetHash(Val1, Val2);
                    CurrSet.Add(NewHash);
                    continue;
                }

                int Val3 = mAArr[I];
                if (IsTousaSuuretu(Val1, Val2, Val3)) {
                    pMinInd = I;
                    return true;
                }
            }
            PrevSet.UnionWith(CurrSet);
        }
        return false;
    }

    // 数値2つを引数としてハッシュ値を返す
    static int GetHash(int pVal1, int pVal2)
    {
        return pVal1 * 100 + pVal2;
    }

    // ハッシュ値を引数として、数値2つに値を設定する
    static void SetVal(int pHash, out int pVal1, out int pVal2)
    {
        pVal1 = pHash / 100;
        pVal2 = pHash % 100;
    }

    // 数値3つを引数とし、等差数列かを返す
    static bool IsTousaSuuretu(int pVal1, int pVal2, int pVal3)
    {
        // 等差中項が中点ならOK
        return pVal2 * 2 == pVal1 + pVal3;
    }
}

解説

項が2個の数列は、10*10 = 100 通りしかないため

項が最大2個の数列の状態のハッシュ値を
更新するDPで解けます。