Educational DP Contest T Permutation

問題へのリンク

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("4");
            WillReturn.Add("<><");
            //5
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("5");
            WillReturn.Add("<<<<");
            //1
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("20");
            WillReturn.Add(">>>><>>><>><>>><<>>");
            //217136290
        }
        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 N = int.Parse(InputList[0]);
        string S = InputList[1];

        // 場合の数[下にあるマス数]なDP表
        int[] PrevDP = new int[N];
        for (int I = 1; I <= N; I++) {
            PrevDP[I - 1] = 1;
        }

        for (int I = 0; I <= S.Length - 1; I++) {
            int[] ImosArr = new int[N];

            for (int J = 0; J <= N - 1; J++) {
                int CurrPetternCnt = PrevDP[J];
                if (CurrPetternCnt == 0) continue;

                int UpperMasuCnt = N - I - J - 1;

                Action<int, int> UpdateAct = (pInd1, pInd2) =>
                {
                    int MinInd = Math.Min(pInd1, pInd2);
                    int MaxInd = Math.Max(pInd1, pInd2);

                    ImosArr[MinInd] += CurrPetternCnt;
                    ImosArr[MinInd] %= Hou;
                    if (MaxInd + 1 <= ImosArr.GetUpperBound(0)) {
                        ImosArr[MaxInd + 1] -= CurrPetternCnt;
                        ImosArr[MaxInd + 1] %= Hou;
                    }
                };

                // 増加の場合
                if (S[I] == '<') {
                    if (UpperMasuCnt == 0) continue;
                    int Ind1 = J;
                    int Ind2 = J + UpperMasuCnt - 1;
                    UpdateAct(Ind1, Ind2);
                }

                // 減少 の場合
                if (S[I] == '>') {
                    if (J == 0) continue;
                    int Ind1 = 0;
                    int Ind2 = J - 1;
                    UpdateAct(Ind1, Ind2);
                }
            }
            for (int J = 1; J <= ImosArr.GetUpperBound(0); J++) {
                ImosArr[J] += ImosArr[J - 1];
                ImosArr[J] %= Hou;
            }
            PrevDP = ImosArr;
        }

        int Answer = 0;
        foreach (int EachInt in PrevDP) {
            Answer += EachInt;
            Answer %= Hou;
        }
        if (Answer < 0) Answer += Hou;
        Console.WriteLine(Answer);
    }
}

解説

場合の数[下にあるマス数]をDPで更新してます。
上にあるマス数は、導出項目になります。

連続した区間への配るDPなので
いもす法を使ってます。