ABC082-D FT Robot

問題へのリンク

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("FTFFTFFF");
            WillReturn.Add("4 2");
            //Yes
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("FTFFTFFF");
            WillReturn.Add("-2 -2");
            //Yes
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("FF");
            WillReturn.Add("1 0");
            //No
        }
        else if (InputPattern == "Input4") {
            WillReturn.Add("TF");
            WillReturn.Add("1 0");
            //No
        }
        else if (InputPattern == "Input5") {
            WillReturn.Add("FFTTFF");
            WillReturn.Add("0 0");
            //Yes
        }
        else if (InputPattern == "Input6") {
            WillReturn.Add("TTTT");
            WillReturn.Add("1 0");
            //No
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static void Main()
    {
        List<string> InputList = GetInputList();

        string S = InputList[0];

        int[] wkArr = InputList[1].Split(' ').Select(A => int.Parse(A)).ToArray();
        int GoalX = wkArr[0];
        int GoalY = wkArr[1];

        var AbsXList = new List<long>();
        var AbsYList = new List<long>();

        string[] SplitArr = S.Split('T');
        for (int I = 0; I <= SplitArr.GetUpperBound(0); I++) {
            if (I % 2 == 0) {
                AbsXList.Add(SplitArr[I].Length);
            }
            else {
                AbsYList.Add(SplitArr[I].Length);
            }
        }

        if (DerivePosSet(true, AbsXList).Contains(GoalX) == false) {
            Console.WriteLine("No");
            return;
        }
        if (DerivePosSet(false, AbsYList).Contains(GoalY) == false) {
            Console.WriteLine("No");
            return;
        }
        Console.WriteLine("Yes");
    }

    // 遷移可能なSetを返す
    static HashSet<long> DerivePosSet(bool pIsX, List<long> pAbsList)
    {
        HashSet<long> PrevSet = new HashSet<long>();
        PrevSet.Add(0);

        bool FirstFlag = true;

        foreach (long EachAbs in pAbsList) {
            HashSet<long> CurrSet = new HashSet<long>();

            foreach (long EachInt in PrevSet) {
                CurrSet.Add(EachInt + EachAbs);

                if (pIsX == false || FirstFlag == false) {
                    CurrSet.Add(EachInt - EachAbs);
                }
            }
            PrevSet = CurrSet;
            FirstFlag = false;
        }
        return PrevSet;
    }
}

解説

X座標とY座標を独立で考え、
遷移可能な座標を動的計画法で求めてます。