TDP F 準急

問題へのリンク

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 2");
            //21
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("10 10");
            //255
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    const long Hou = 1000000007;

    static void Main()
    {
        List<string> InputList = GetInputList();
        long[] wkArr = InputList[0].Split(' ').Select(pX => long.Parse(pX)).ToArray();
        long N = wkArr[0];
        long K = wkArr[1];

        Solve(N, K);
    }

    static void Solve(long pN, long pK)
    {
        var InsLinkedList = new LinkedList<long>();
        InsLinkedList.AddFirst(1);
        InsLinkedList.AddFirst(0);
        long PrevSum = 1;

        for (long I = 2; I <= pN; I++) {
            InsLinkedList.AddFirst(PrevSum);
            long CurrSum = PrevSum; // 連続数0には、1駅前の総合計が遷移

            if (InsLinkedList.Count > pK) {
                PrevSum -= InsLinkedList.Last.Value;
                if (PrevSum < 0) PrevSum += Hou;
                InsLinkedList.RemoveLast();
            }
            CurrSum += PrevSum;
            CurrSum %= Hou;
            PrevSum = CurrSum;
        }

        // 最後の駅で、連続数1以上の総和が解
        long Answer = 0;
        foreach (long EachLong in InsLinkedList.Skip(1)) {
            Answer += EachLong;
            Answer %= Hou;
        }
        Console.WriteLine(Answer);
    }
}

解説

Y軸に連続停車数、X軸を駅の位置とし、
最大の連続停車数が3だとすると
下記の様な、場合の数の分布となります。

3駅     1 0 1  2  4  7
2駅   1 0 1 2  4  7 14
1駅 1 0 1 2 4  7 14 27
0駅 0 1 2 4 7 14 27 52
----------------------
    1 2 3 4 5  6  7  8

0駅には、その駅で止まらなければいいだけなので
1駅前の、全ての状態から遷移できると分かります。

また、
連続数は、右上に同じ数が遷移していくことも分かります。

後は、LinkedListで駅ごとの値を管理しつつ、
合計も管理すれば、解くことができます。