Q68 隣り合わないのがマナー

C#のソース

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static void Main()
    {
        //場合の数[座席の状態]なDP表
        var PrevDP = new Dictionary<string, int>();
        PrevDP["*SSSSSS*SSSSSS*"] = 1;

        int AnswerCnt = 0;
        int DPCnt = 0;
        while (PrevDP.Count > 0) {
            var CurrDP = new Dictionary<string, int>();
            foreach (var EachPair in PrevDP) {
                bool HasRyoudonariSpace = false;
                for (int I = 0; I <= EachPair.Key.Length - 1; I++) {
                    //両隣が空席な、空席の場合
                    if (IsRyoudonariSpace(EachPair.Key, I)) {
                        HasRyoudonariSpace = true;
                        string NewKey = EachPair.Key;
                        NewKey = NewKey.Remove(I, 1).Insert(I, "F");

                        if (CurrDP.ContainsKey(NewKey))
                            CurrDP[NewKey] += EachPair.Value;
                        else CurrDP[NewKey] = EachPair.Value;
                    }
                }

                //両隣が空席な、空席が1つもなかった場合
                if (HasRyoudonariSpace == false) {
                    int SpaceCnt = EachPair.Key.Count(X => X == 'S');
                    //積の法則で求めた場合の数を、和の法則で計上
                    AnswerCnt += EachPair.Value * DeriveKaijyou(SpaceCnt);
                }
            }
            Console.WriteLine("{0}回目のDPの結果", ++DPCnt);
            PrintDP(CurrDP);
            PrevDP = CurrDP;
        }
        Console.WriteLine("答えは{0}通り", AnswerCnt);
    }

    //両隣が空席な、空席かを返す
    static bool IsRyoudonariSpace(string pJyoutaiStr, int pCurrInd)
    {
        if (pJyoutaiStr[pCurrInd] != 'S') return false;
        if (pJyoutaiStr[pCurrInd - 1] == 'F') return false;
        if (pJyoutaiStr[pCurrInd + 1] == 'F') return false;
        return true;
    }

    //階乗を求める
    static int DeriveKaijyou(int pTarget)
    {
        int WillReturn = 1;
        for (int I = 2; I <= pTarget; I++)
            WillReturn *= I;
        return WillReturn;
    }

    static void PrintDP(Dictionary<string, int> pDPDict)
    {
        foreach (var EachPair in pDPDict) {
            Console.WriteLine("{0}の場合の数={1}",
                EachPair.Key, EachPair.Value);
        }
    }
}

実行結果

省略
6回目のDPの結果
*FSFSFS*FSFSFS*の場合の数=720
*FSFSFS*FSFSSF*の場合の数=720
*FSFSFS*FSSFSF*の場合の数=720
*FSFSFS*SFSFSF*の場合の数=720
*FSFSSF*FSFSFS*の場合の数=720
*FSFSSF*FSFSSF*の場合の数=720
*FSFSSF*FSSFSF*の場合の数=720
*FSFSSF*SFSFSF*の場合の数=720
*FSSFSF*FSFSFS*の場合の数=720
*FSSFSF*FSFSSF*の場合の数=720
*FSSFSF*FSSFSF*の場合の数=720
*FSSFSF*SFSFSF*の場合の数=720
*SFSFSF*FSFSFS*の場合の数=720
*SFSFSF*FSFSSF*の場合の数=720
*SFSFSF*FSSFSF*の場合の数=720
*SFSFSF*SFSFSF*の場合の数=720
7回目のDPの結果
答えは14100480通り

解説

和の法則や積の法則で、場合の数を更新する動的計画法を使ってます。