三井住友信託銀行プログラミングコンテスト2019 E Colorful Hats 2

問題へのリンク

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("6");
            WillReturn.Add("0 1 2 3 4 5");
            //3
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("3");
            WillReturn.Add("0 0 0");
            //6
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("54");
            WillReturn.Add("0 0 1 0 1 2 1 2 3 2 3 3 4 4 5 4 6 5 7 8 5 6 6 7 7 8 8 9 9 10 10 11 9 12 10 13 14 11 11 12 12 13 13 14 14 15 15 15 16 16 16 17 17 17");
            //115295190
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    const long Hou = 1000000007;

    static void Main()
    {
        List<string> InputList = GetInputList();
        long[] AArr = InputList[1].Split(' ').Select(pX => long.Parse(pX)).ToArray();

        var CntDict = new Dictionary<char, long>();
        CntDict['R'] = 0;
        CntDict['G'] = 0;
        CntDict['B'] = 0;

        long Answer = 1;
        foreach (long EachA in AArr) {
            // 個数が一致する色が何色あるかを調べる
            long KouhoColorCnt = CntDict.Values.Count(pX => pX == EachA);

            // 場合の数の積の法則
            Answer *= KouhoColorCnt;
            Answer %= Hou;
            //Console.WriteLine("KouhoColorCnt={0},Answer={1}", KouhoColorCnt, Answer);

            foreach (char EachKey in CntDict.Keys) {
                if (CntDict[EachKey] == EachA) {
                    CntDict[EachKey]++;
                    break;
                }
            }
        }
        Console.WriteLine(Answer);
    }
}

解説

3色ではなく
チェスセットで白と黒の2色のポーンを使って
先頭から、白ポーン優先で設置する形で考察します。

   0 1 0 1 2 といった場合は
白 1 2 2 2 3
黒 0 0 1 2 2
となります。

樹形図をイメージすると、
白優先で設置したので、黒も可能だった場所では、
場合の数の積の法則で、解に2を掛ける必要があります。