Problem679 各文字列が1回ずつ現れる文字列の個数

問題

長さnで A, E, F, R からなる文字列のうち、
4つのキーワード FREE, FARE, AREA, REEF を各1回ずつ含むものはいくつあるか。
n=30について求めよ。

ソース

using System;
using System.Collections.Generic;

class Program
{
    struct JyoutaiDef
    {
        internal bool AppearFREE;
        internal bool AppearFARE;
        internal bool AppearAREA;
        internal bool AppearREEF;
        internal string Last4Str;
    }

    //ハッシュ値をJyoutaiDef型に変換
    static JyoutaiDef HashToJyoutai(string pHash)
    {
        JyoutaiDef WillReturn;
        WillReturn.AppearFREE = (pHash[0] == '1');
        WillReturn.AppearFARE = (pHash[1] == '1');
        WillReturn.AppearAREA = (pHash[2] == '1');
        WillReturn.AppearREEF = (pHash[3] == '1');
        WillReturn.Last4Str = pHash.Substring(4);
        return WillReturn;
    }

    //JyoutaiDef型をハッシュ値に変換
    static string JyoutaiToHash(JyoutaiDef pJyoutai)
    {
        string WillReturn = "";
        WillReturn += (pJyoutai.AppearFREE ? "1" : "0");
        WillReturn += (pJyoutai.AppearFARE ? "1" : "0");
        WillReturn += (pJyoutai.AppearAREA ? "1" : "0");
        WillReturn += (pJyoutai.AppearREEF ? "1" : "0");
        WillReturn += pJyoutai.Last4Str;
        return WillReturn;
    }

    static void Main()
    {
        Solve(9);
        Solve(15);
        Solve(30);
    }

    static void Solve(int pN)
    {
        //場合の数[状態のハッシュ値]なDP表
        var PrevDP = new Dictionary<string, long>();
        PrevDP["0000"] = 1;
        for (int I = 1; I <= pN; I++) {
            var CurrDP = new Dictionary<string, long>();
            foreach (var EachPair in PrevDP) {
                JyoutaiDef OldJyoutai = HashToJyoutai(EachPair.Key);
                foreach (char EachChar in "AEFR") {
                    JyoutaiDef NewJyoutai = OldJyoutai;
                    NewJyoutai.Last4Str += EachChar.ToString();
                    if (NewJyoutai.Last4Str.Length > 4) {
                        NewJyoutai.Last4Str = NewJyoutai.Last4Str.Substring(1, 4);
                    }

                    if (NewJyoutai.Last4Str == "FREE") {
                        if (OldJyoutai.AppearFREE) continue;
                        NewJyoutai.AppearFREE = true;
                    }
                    if (NewJyoutai.Last4Str == "FARE") {
                        if (OldJyoutai.AppearFARE) continue;
                        NewJyoutai.AppearFARE = true;
                    }
                    if (NewJyoutai.Last4Str == "AREA") {
                        if (OldJyoutai.AppearAREA) continue;
                        NewJyoutai.AppearAREA = true;
                    }
                    if (NewJyoutai.Last4Str == "REEF") {
                        if (OldJyoutai.AppearREEF) continue;
                        NewJyoutai.AppearREEF = true;
                    }

                    string NewHash = JyoutaiToHash(NewJyoutai);
                    if (CurrDP.ContainsKey(NewHash))
                        CurrDP[NewHash] += EachPair.Value;
                    else CurrDP[NewHash] = EachPair.Value;
                }
            }
            PrevDP = CurrDP;
        }

        long Answer = 0;
        foreach (var EachPair in PrevDP) {
            if (EachPair.Key.StartsWith("1111")) {
                Answer += EachPair.Value;
            }
        }
        Console.WriteLine("N={0}だと{1}通り", pN, Answer);
    }
}

実行結果

N=9だと1通り
N=15だと72863通り
N=30だと644997092988678通り

解説

"FREE"、"FARE"、"AREA"、"REEF"の登場有無と、
末尾4文字を状態に持って、動的計画法で解いてます。