ARC-033-A 隠れた言葉

■■■問題■■■

高橋君は、隠れた言葉を探す遊びが好きです。
例えば、「じきゅうりょく」の中には「きゅうり」という言葉が隠れています。

高橋君は今、長さNの文字列の中に隠れた言葉を探そうとしています。
隠れた言葉の候補を列挙するためにまず、
この文字列の「部分文字列」の個数を計算してみることにしました。

文字列Sの「部分文字列」とは、
文字列Sに含まれるある区間を取り出した文字列のことです。
例えば、「すぬけ」の部分文字列は「す」「ぬ」「け」「すぬ」「ぬけ」「すぬけ」の6つです。
「すけ」や「ぬす」などは部分文字列ではないことに注意してください。

また、文字列Sには同じ文字が2回以上現れないことが分かっています。
そのため「しょうぼうしょ」における「しょ」のように、
異なる場所から取り出した文字列が一致することはありません。

■■■入力■■■

N

1行目には、文字列の長さを表す整数 N(1 <= N <= 1000) が与えられる。

■■■出力■■■

長さNの文字列の「部分文字列」の個数を1行に出力せよ。出力の末尾に改行を入れること。

C#のソース

using System;
using System.Collections.Generic;

class Program
{
    static string InputPattern = "InputX";

    static List<string> GetInputList()
    {
        var WillReturn = new List<string>();

        if (InputPattern == "Input1") {
            WillReturn.Add("1");
            //1
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("2");
            //3
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("3");
            //6
            //問題文中で示した「すぬけ」の例の通り、
            //6つの部分文字列があります。
        }
        else if (InputPattern == "Input4") {
            WillReturn.Add("4");
            //10
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static void Main()
    {
        List<string> InputList = GetInputList();
        int N = int.Parse(InputList[0]);

        var CntDict = new Dictionary<int, int>();
        CntDict[1] = 1;
        for (int I = 2; I <= N; I++) {
            CntDict[I] = I + CntDict[I - 1];
        }
        Console.WriteLine(CntDict[N]);
    }
}

解説

文字列が1文字の場合は、1通り
文字列が2文字の場合は、先頭文字を含む文字列は2通り
                       先頭文字を含まない文字列は、文字列が1文字の場合と同じ
文字列が3文字の場合は、先頭文字を含む文字列は3通り
                       先頭文字を含まない文字列は、文字列が2文字の場合と同じ
文字列が4文字の場合は、先頭文字を含む文字列は4通り
                       先頭文字を含まない文字列は、文字列が3文字の場合と同じ
として、漸化式で解いてます。