エクサウィザーズ 2019 C Snuke the Wizard

問題へのリンク

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 4");
            WillReturn.Add("ABC");
            WillReturn.Add("A L");
            WillReturn.Add("B L");
            WillReturn.Add("B R");
            WillReturn.Add("A R");
            //2
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("8 3");
            WillReturn.Add("AABCBDBA");
            WillReturn.Add("A L");
            WillReturn.Add("B R");
            WillReturn.Add("A R");
            //5
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("10 15");
            WillReturn.Add("SNCZWRCEWB");
            WillReturn.Add("B R");
            WillReturn.Add("R R");
            WillReturn.Add("E R");
            WillReturn.Add("W R");
            WillReturn.Add("Z L");
            WillReturn.Add("S R");
            WillReturn.Add("Q L");
            WillReturn.Add("W L");
            WillReturn.Add("B R");
            WillReturn.Add("C L");
            WillReturn.Add("A L");
            WillReturn.Add("N L");
            WillReturn.Add("E R");
            WillReturn.Add("Z L");
            WillReturn.Add("S L");
            //3
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static string mS;

    struct TDInfoDef
    {
        internal char T;
        internal char D;
    }
    static List<TDInfoDef> mTDInfoList = new List<TDInfoDef>();

    static int UB;

    static void Main()
    {
        List<string> InputList = GetInputList();
        mS = InputList[1];
        UB = mS.Length - 1;

        foreach (string EachStr in InputList.Skip(2)) {
            TDInfoDef WillAdd;
            string[] SplitArr = EachStr.Split(' ');
            WillAdd.T = SplitArr[0][0];
            WillAdd.D = SplitArr[1][0];
            mTDInfoList.Add(WillAdd);
        }

        int Result1 = ExecNibunhou1();
        int Result2 = ExecNibunhou2();
        int DropLeftCnt = Result1 + 1;
        int DropRightCnt = UB - Result2 + 1;
        //Console.WriteLine("Result1={0},DropLeftCnt={1}", Result1, DropLeftCnt);
        //Console.WriteLine("Result2={0},DropRightCnt={1}", Result2, DropRightCnt);

        Console.WriteLine(mS.Length - DropLeftCnt - DropRightCnt);
    }

    // 二分法で、左端を超えれる最大の添字を返す
    static int ExecNibunhou1()
    {
        // 最後の要素が左端を越えれる特殊ケース
        if (WillOverLeft(UB)) {
            return UB;
        }

        // 最初の要素が左端を越えれない特殊ケース
        if (WillOverLeft(0) == false) {
            return -1;
        }

        int L = 0;
        int R = UB;

        while (L + 1 < R) {
            int Mid = (L + R) / 2;

            if (WillOverLeft(Mid)) {
                L = Mid;
            }
            else {
                R = Mid;
            }
        }
        return L;
    }

    // 二分法で、右端を超えれる最大の添字を返す
    static int ExecNibunhou2()
    {
        // 最後の要素が右端を越えれない特殊ケース
        if (WillOverRight(UB) == false) {
            return UB + 1;
        }

        // 最初の要素が右端を越えれる特殊ケース
        if (WillOverRight(0)) {
            return 0;
        }

        int L = 0;
        int R = UB;

        while (L + 1 < R) {
            int Mid = (L + R) / 2;

            if (WillOverRight(Mid)) {
                R = Mid;
            }
            else {
                L = Mid;
            }
        }
        return R;
    }

    // 指定した添字が、左端を超えるかを判定
    static bool WillOverLeft(int pInd)
    {
        int CurrInd = pInd;
        foreach (TDInfoDef EachTDInfo in mTDInfoList) {
            char CurrChar = mS[CurrInd];
            if (EachTDInfo.T == CurrChar) {
                if (EachTDInfo.D == 'L') {
                    CurrInd--;
                }
                else {
                    CurrInd++;
                }
                if (CurrInd < 0) return true;
                if (UB < CurrInd) return false;
            }
        }
        return false;
    }

    // 指定した添字が、右端を超えるかを判定
    static bool WillOverRight(int pInd)
    {
        int CurrInd = pInd;
        foreach (TDInfoDef EachTDInfo in mTDInfoList) {
            char CurrChar = mS[CurrInd];
            if (EachTDInfo.T == CurrChar) {
                if (EachTDInfo.D == 'R') {
                    CurrInd++;
                }
                else {
                    CurrInd--;
                }
                if (CurrInd < 0) return false;
                if (UB < CurrInd) return true;
            }
        }
        return false;
    }
}

解説

配列を左から見ていった場合に、
その添字のゴーレムが左端から落ちるか
は、単調性があります。

同様に、
配列を左から見ていった場合に、
その添字のゴーレムが右端から落ちるか
も、単調性があります。

以上をふまえて、二分法を2回使ってます。