13回予選 D 部活のスケジュール表

問題へのリンク

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("2");
            WillReturn.Add("OI");
            //7
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("20");
            WillReturn.Add("JIOIJOIJOJOIIIOJIOII");
            //4976
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    const long Hou = 10007;

    static void Main()
    {
        List<string> InputList = GetInputList();
        char[] SArr = InputList[1].ToCharArray();

        var KouhoStrList = new List<string>();
        KouhoStrList.Add("J");
        KouhoStrList.Add("O");
        KouhoStrList.Add("I");
        KouhoStrList.Add("JO");
        KouhoStrList.Add("JI");
        KouhoStrList.Add("OI");
        KouhoStrList.Add("JOI");

        // 場合の数[前日の出席者]なDP表
        var PrevDP = new Dictionary<string, long>();
        PrevDP["J"] = 1;

        foreach (char TodayChar in SArr) {
            var CurrDP = new Dictionary<string, long>();
            foreach (var EachPair in PrevDP) {
                foreach (string EachKouhoStr in KouhoStrList) {
                    // 責任者は出席必須
                    if (EachKouhoStr.Contains(TodayChar) == false) {
                        continue;
                    }

                    // 前日の出席者と共通の人が必要
                    if (HasCommonChar(EachPair.Key, EachKouhoStr) == false) {
                        continue;
                    }

                    if (CurrDP.ContainsKey(EachKouhoStr) == false) {
                        CurrDP[EachKouhoStr] = 0;
                    }
                    CurrDP[EachKouhoStr] += EachPair.Value;
                    CurrDP[EachKouhoStr] %= Hou;
                }
            }
            PrevDP = CurrDP;
        }

        long Answer = 0;
        foreach (var EachPair in PrevDP) {
            Answer += EachPair.Value;
            Answer %= Hou;
        }
        Console.WriteLine(Answer);
    }

    // 文字列2つを引数として共通の文字があるかを判定
    static bool HasCommonChar(string pStr1, string pStr2)
    {
        foreach (char EachChar1 in pStr1) {
            foreach (char EachChar2 in pStr2) {
                if (EachChar1 == EachChar2) return true;
            }
        }
        return false;
    }
}

解説

場合の数[前日の出席者]でDPしてます。