典型90問    次の典型90問へ    前の典型90問へ

典型90問 008 AtCounter(★4)


問題へのリンク


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");
            WillReturn.Add("attcordeer");
            //4
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("41");
            WillReturn.Add("btwogablwetwoiehocghiewobadegwhoihegnldir");
            //2
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("140");
            WillReturn.Add("aaaaaaaaaaaaaaaaaaaattttttttttttttttttttccccccccccccccccccccooooooooooooooooooooddddddddddddddddddddeeeeeeeeeeeeeeeeeeeerrrrrrrrrrrrrrrrrrrr");
            //279999993
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    const int Hou = 1000000007;

    static void Main()
    {
        List<string> InputList = GetInputList();
        string S = InputList[1];

        // 場合の数[現在位置]なDP表
        //  atcoder 
        // 01234567
        int[] DPArr = new int[8];
        DPArr[0] = 1;

        foreach (char EachChar in S) {
            for (int I = 6; 0 <= I; I--) {
                if (DPArr[I] == 0) continue;

                Action AddAct = () =>
                {
                    DPArr[I + 1] += DPArr[I];
                    DPArr[I + 1] %= Hou;
                };
                if (I == 0 && EachChar == 'a') AddAct();
                if (I == 1 && EachChar == 't') AddAct();
                if (I == 2 && EachChar == 'c') AddAct();
                if (I == 3 && EachChar == 'o') AddAct();
                if (I == 4 && EachChar == 'd') AddAct();
                if (I == 5 && EachChar == 'e') AddAct();
                if (I == 6 && EachChar == 'r') AddAct();
            }
        }
        Console.WriteLine(DPArr[7]);
    }
}


解説

場合の数[現在位置]を更新するインラインDPで解けます。