Problem191 賞を貰える文字列

問題

ある学校では出席率が高く遅刻率が低い生徒に褒賞金を出している.
3日連続で休む, または,
2回以上遅刻した生徒は褒賞金を得る権利を失う.

n日間の各生徒の出席状況を3進の文字列で表す.
文字はL (late, 遅刻),O (on time, 出席), A (absent, 欠席) である.

4日間の場合, 81通りの3進の文字列が考えられる. そのうち賞を貰えるのは以下の43個の文字列である.

OOOO OOOA OOOL OOAO OOAA OOAL OOLO OOLA OAOO OAOA
OAOL OAAO OAAL OALO OALA OLOO OLOA OLAO OLAA AOOO
AOOA AOOL AOAO AOAA AOAL AOLO AOLA AAOO AAOA AAOL
AALO AALA ALOO ALOA ALAO ALAA LOOO LOOA LOAO LOAA
LAOO LAOA LAAO
30日間の場合, 賞を貰える文字列は何通りか?

ソース(ナイーブな深さ優先探索)

using System;
using System.Collections.Generic;

class Program
{
    //const int Days = 4;
    const int Days = 30;

    static void Main()
    {
        var sw = System.Diagnostics.Stopwatch.StartNew();
        var Stk = new Stack<string>();

        Stk.Push("L");
        Stk.Push("O");
        Stk.Push("A");

        int AnsCnt = 0;

        while (Stk.Count > 0) {
            string Popped = Stk.Pop();

            if (Popped.Length == Days) {
                AnsCnt++;
                if (AnsCnt % 10000000 == 0) {
                    Console.WriteLine("経過時間={0},スタック数={1},解の数={2}",
                                      sw.Elapsed,Stk.Count, AnsCnt);
                }
                continue;
            }

            if (Popped.Contains("L") == false) Stk.Push(Popped + "L");
            Stk.Push(Popped + "O");
            if (Popped.EndsWith("AA") == false) Stk.Push(Popped + "A");
        }
        Console.WriteLine("経過時間={0},スタック数={1},解の数={2}", sw.Elapsed,Stk.Count, AnsCnt);
    }
}

実行結果(ナイーブな深さ優先探索)

省略
経過時間=00:52:01.7188896,スタック数=11,解の数=1880000000
経過時間=00:52:16.8797486,スタック数=14,解の数=1890000000
経過時間=00:52:32.0295255,スタック数=12,解の数=1900000000
経過時間=00:52:47.1761768,スタック数=9,解の数=1910000000
経過時間=00:52:59.4252216,スタック数=0,解の数=1918080160

ソース(深さ優先探索の速度改善版)

using System;
using System.Collections.Generic;

class Program
{
    //const int Days = 4;
    const int Days = 30;

    struct JyoutaiDef
    {
        internal int Level;
        internal int OCnt;
        internal int LastSeqACnt;
    }

    static void Main()
    {
        var sw = System.Diagnostics.Stopwatch.StartNew();
        var Stk = new Stack<JyoutaiDef>();

        JyoutaiDef WillPush;
        WillPush.Level = 1;

        //Oの場合
        WillPush.OCnt = 1;
        WillPush.LastSeqACnt = 0;
        Stk.Push(WillPush);

        //Aの場合
        WillPush.OCnt = 0;
        WillPush.LastSeqACnt = 1;
        Stk.Push(WillPush);

        int LeafCnt = 0;
        int AnsCnt = 0;

        while (Stk.Count > 0) {
            JyoutaiDef Popped = Stk.Pop();

            if (Popped.Level == Days) {
                LeafCnt++;
                AnsCnt++;

                //仮置きしたOを1個だけLに置き換えた組み合わせの数
                AnsCnt += Popped.OCnt;
                continue;
            }

            //Oの場合
            WillPush.Level = Popped.Level + 1;
            WillPush.OCnt = Popped.OCnt + 1;
            WillPush.LastSeqACnt = 0;
            Stk.Push(WillPush);

            //Aの場合
            if (Popped.LastSeqACnt <= 1) {
                WillPush.Level = Popped.Level + 1;
                WillPush.OCnt = Popped.OCnt;
                WillPush.LastSeqACnt = Popped.LastSeqACnt + 1;
                Stk.Push(WillPush);
            }
        }
        Console.WriteLine("経過時間={0},解の数={1},葉ノード数={2}",
            sw.Elapsed, AnsCnt, LeafCnt);
    }
}

実行結果(深さ優先探索の速度改善版)

経過時間=00:00:11.0251230,解の数=1918080160,葉ノード数=98950096

ソース(動的計画法)

using System;
using System.Linq;

class Program
{
    //const int Days = 4;
    const int Days = 30;

    static void Main()
    {
        var sw = System.Diagnostics.Stopwatch.StartNew();

        //場合の数[直近のA][Lの数]なDP表
        int[,] PrevDP = new int[3, 2];
        PrevDP[0, 0] = 1;

        for (int I = 1; I <= Days; I++) {
            int[,] CurrDP = new int[3, 2];

            for (int J = 0; J <= PrevDP.GetUpperBound(0); J++) {
                for (int K = 0; K <= PrevDP.GetUpperBound(1); K++) {
                    if (PrevDP[J, K] == 0) continue;

                    //Oの場合
                    CurrDP[0, K] += PrevDP[J, K];

                    //Aの場合
                    if (J <= 1)
                        CurrDP[J + 1, K] += PrevDP[J, K];

                    //Lの場合
                    if (K == 0)
                        CurrDP[0, K + 1] += PrevDP[J, K];
                }
            }

            Console.WriteLine("{0}日目の場合の数", I);
            for (int J = 0; J <= PrevDP.GetUpperBound(0); J++) {
                for (int K = 0; K <= PrevDP.GetUpperBound(1); K++) {
                    if (CurrDP[J, K] == 0) continue;
                    Console.WriteLine("CurrDP[{0},{1}]={2}",
                        J, K, CurrDP[J, K]);
                }
            }

            PrevDP = CurrDP;
        }
        Console.WriteLine("解は{0}", PrevDP.Cast<int>().Sum());
    }
}

実行結果(動的計画法)

省略
30日目の場合の数
CurrDP[0,0]=53798080
CurrDP[0,1]=1009569304
CurrDP[1,0]=29249425
CurrDP[1,1]=530803311
CurrDP[2,0]=15902591
CurrDP[2,1]=278757449
解は1918080160

解説

深さ優先探索の速度改善版では、
手順1 Aの場所を決める。(A以外の場所は、Oを仮置き)
手順2 仮置きしたOを1個だけLに置き換えた組み合わせの数を求める
といった手順で、組み合わせの合計を求めてます。