ABC017-D サプリメント

問題へのリンク

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

    const int Hou = 1000000007;

    static void Main()
    {
        List<string> InputList = GetInputList();

        int[] FArr = InputList.Skip(1).Select(pX => int.Parse(pX)).ToArray();
        long Answer = Solve(FArr);
        Console.WriteLine(Answer);
    }

    static long Solve(int[] pFArr)
    {
        // 処理01 尺取法を使う
        int[] SyakutorihouArr = DeriveSyakutorihouArr(pFArr);

        // 処理02 いもす法での、加算添字と減算添字をListにまとめる
        var ImosIndInfoDict = new Dictionary<int, ImosIndInfoDef>();
        for (int I = 0; I <= pFArr.GetUpperBound(0); I++) {
            var WillSet = new ImosIndInfoDef();
            WillSet.ImosStaInd = I + 1;
            WillSet.ImosEndInd = SyakutorihouArr[I] + 1 + 1;
            if (WillSet.ImosStaInd == WillSet.ImosEndInd) {
                WillSet.ImosEndInd++;
            }
            ImosIndInfoDict[I] = WillSet;
        }

        // 処理03
        int[] DPArr = new int[pFArr.Length];
        int[] ImosArr = new int[pFArr.Length];
        DPArr[0] = 1;
        ImosArr[0] = 0;

        int Answer = 0;
        for (int I = 0; I <= pFArr.GetUpperBound(0); I++) {
            if (I > 0) {
                ImosArr[I] += ImosArr[I - 1];
                ImosArr[I] %= Hou;
                DPArr[I] = ImosArr[I];
            }
            ImosIndInfoDef CurrImosIndInfo = ImosIndInfoDict[I];
            int ImosStaInd = CurrImosIndInfo.ImosStaInd;
            int ImosEndInd = CurrImosIndInfo.ImosEndInd;

            if (ImosStaInd <= pFArr.GetUpperBound(0)) {
                ImosArr[ImosStaInd] += DPArr[I];
                ImosArr[ImosStaInd] %= Hou;
            }
            if (pFArr.GetUpperBound(0) + 1 < ImosEndInd) {
                Answer += DPArr[I];
                Answer %= Hou;
            }
            if (ImosEndInd <= pFArr.GetUpperBound(0)) {
                ImosArr[ImosEndInd] -= DPArr[I];
                ImosArr[ImosEndInd] += Hou;
                ImosArr[ImosEndInd] %= Hou;
            }
        }

        return Answer;
    }

    class ImosIndInfoDef
    {
        internal int ImosStaInd;
        internal int ImosEndInd;
    }

    // 尺取法で、同じ数値が現れない最大添字[現在添字] を求める
    static int[] DeriveSyakutorihouArr(int[] pArr)
    {
        int[] SyakutorihouArr = new int[pArr.Length];

        var FSet = new HashSet<int>();
        FSet.Add(pArr[0]);

        int R = 0;
        int UB = pArr.GetUpperBound(0);
        for (int L = 0; L <= UB; L++) {
            while (R + 1 <= UB && FSet.Add(pArr[R + 1])) {
                R++;
            }
            SyakutorihouArr[L] = R;
            FSet.Remove(pArr[L]);
        }
        return SyakutorihouArr;
    }

    static long SolveNaive(int[] pFArr)
    {
        int UB = pFArr.GetUpperBound(0);

        // 場合の数[現在の添字]なDP表
        int[] DPArr = new int[UB + 1];
        DPArr[0] = 1;

        int Answer = 0;
        for (int I = 0; I <= UB; I++) {
            var FSet = new HashSet<int>();
            for (int J = I; J <= UB; J++) {
                if (FSet.Add(pFArr[J]) == false) break;

                int NewInd = J + 1;
                if (NewInd <= UB) {
                    DPArr[NewInd] += DPArr[I];
                }
                else {
                    Answer += DPArr[I];
                }
            }
        }
        return Answer;
    }
}

解説

場合の数[摂取開始の添字]を更新する、ナイーブな配るDPを
尺取法といもす法で高速化してます。