ARC175-A Spoon Taking Problem

問題へのリンク

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

    const long Hou = 998244353;

    static long[] mPArr;
    static long mN;
    static char[] mSArr;
    static long mFirstMan;

    static void Main()
    {
        List<string> InputList = GetInputList();
        mPArr = InputList[1].Split(' ').Select(pX => long.Parse(pX)).ToArray();
        mN = long.Parse(InputList[0]);
        mSArr = InputList[2].ToCharArray();
        mFirstMan = mPArr[0];

        var AnswerList = new List<long>();
        if (mSArr[mFirstMan - 1] == 'L') {
            AnswerList.Add(Solve('L'));
        }
        if (mSArr[mFirstMan - 1] == 'R') {
            AnswerList.Add(Solve('R'));
        }
        if (mSArr[mFirstMan - 1] == '?') {
            AnswerList.Add(Solve('L'));
            AnswerList.Add(Solve('R'));
        }

        long Answer = 0;
        AnswerList.ForEach(pX =>
        {
            Answer += pX; Answer %= Hou;
        });

        Console.WriteLine(Answer);
    }

    // 最初の方向を引数として、解を返す
    static long Solve(char FirstVector)
    {
        long Answer = 1;

        var BanDict = new Dictionary<long, char>();
        for (long I = 1; I <= 2 * mN; I++) {
            if (I % 2 == 1) {
                BanDict[I] = 'ス';
            }
            else {
                BanDict[I] = mSArr[I / 2 - 1];
            }
        }

        foreach (long EachMan in mPArr) {
            char Kikiude = mSArr[EachMan - 1];

            bool CanL = false;
            bool CanR = false;
            if (FirstVector == 'L') CanL = true;
            if (FirstVector == 'R') CanR = true;

            long LeftPos = EachMan * 2 - 1;
            if (BanDict[LeftPos] == '空') {
                CanL = true;
            }

            long RightPos = EachMan * 2 + 1;
            if (RightPos > 2 * mN) RightPos = 1;
            if (BanDict[RightPos] == '空') {
                CanR = true;
            }

            long ProdVal = 0;
            if (Kikiude == '?') {
                if (CanL) ProdVal++;
                if (CanR) ProdVal++;
            }
            if (Kikiude == 'L') {
                if (CanL) ProdVal++;
            }
            if (Kikiude == 'R') {
                if (CanR) ProdVal++;
            }

            if (ProdVal == 0) return 0;

            Answer *= ProdVal;
            Answer %= Hou;

            if (FirstVector == 'L') {
                BanDict[LeftPos] = '空';
            }
            if (FirstVector == 'R') {
                BanDict[RightPos] = '空';
            }
        }
        return Answer;
    }
}

解説

最初の人が右から取ったら、全員右から取る必要があります。
最初の人が左から取ったら、全員左から取る必要があります。

これをふまえ、
スプーンの有無をシュミレーションしつつ、
場合の数の積の法則を使ってます。