ABC-035-B ドローン

■■■問題■■■

無限に広い二次元グリッドの原点(0,0)に高橋君と1台のドローンがいます。
このドローンは文字列が与えられた時、
文字列の先頭から末尾までのそれぞれの文字を1つの命令と解釈して順に実行します。
命令は以下の4種類です。

●'L' 現在のドローンの位置を(x,y)として(x-1,y)に移動する
●'R' 現在のドローンの位置を(x,y)として(x+1,y)に移動する
●'U' 現在のドローンの位置を(x,y)として(x,y+1)に移動する
●'D' 現在のドローンの位置を(x,y)として(x,y-1)に移動する

今、ドローンに何らかの命令が与えられ、どこかへと移動しました。
高橋君はドローンに送られた命令を表す文字列であるSを手に入れたものの、
いくつかの箇所は破損し'?'になり分からなくなってしまいました。
ただし、'?'が元々は'L'、'R'、'U'、'D'のいずれかの文字だったことが分かっています。

ドローンと高橋君の距離はドローンの位置を(x,y)として
マンハッタン距離 |x|+|y| で表されます。

求める値の種類を表す整数Tが与えられるので、
移動を終えたあとのドローンと高橋君の距離としてありうる値のうち、
T=1ならば最大値を、T=2ならば最小値を求めてください。

■■■入力■■■

S
T

●1行目にドローンに与えられた命令を表す文字列 S(1 <= |S| <= 10万) が与えられる。
  ここで、 |S| は文字列 S の長さを表す。
●Sは'L'、'R'、'U'、'D'、'?'の5種類の文字のみからなる。
●2行目に求める値の種類を表す整数 T(1 <= T <= 2) が与えられる。

■■■出力■■■

●T=1ならば移動を終えたあとのドローンと高橋君の距離としてありうる値のうち、最大値を1行に出力せよ。
●T=2ならば移動を終えたあとのドローンと高橋君の距離としてありうる値のうち、最小値を1行に出力せよ。

C#のソース

using System;
using System.Collections.Generic;

class Program
{
    static string InputPattern = "Input1";

    static List<string> GetInputList()
    {
        var WillReturn = new List<string>();

        if (InputPattern == "Input1") {
            WillReturn.Add("UL?");
            WillReturn.Add("1");
            //3
            //ドローンが最終的にいる可能性がある位置は
            //(-2,1),(-1,0),(-1,2),(0,1)の4つです。
            //ドローンと高橋君の距離 |x|+|y| のうち最大値は3となります。
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("UD?");
            WillReturn.Add("1");
            //1
            //ドローンが最終的にいる可能性がある位置は
            //(1,0),(-1,0),(0,1),(0,-1) の 4 つです。
            //ドローンと高橋君の距離 |x|+|y| のうち最大値は1となります。
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("UUUU?DDR?LLLL");
            WillReturn.Add("1");
            //7
        }
        else if (InputPattern == "Input4") {
            WillReturn.Add("UULL?");
            WillReturn.Add("2");
            //3
        }
        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 T = int.Parse(InputList[1]);

        int CurrX = 0;
        int CurrY = 0;
        int HatenaCnt = 0;
        foreach (char EachChar in S) {
            if (EachChar == 'L') CurrX--;
            if (EachChar == 'R') CurrX++;
            if (EachChar == 'U') CurrY++;
            if (EachChar == 'D') CurrY--;
            if (EachChar == '?') HatenaCnt++;
        }

        for (int I = 1; I <= HatenaCnt; I++) {
            if (T == 1) { //原点からの距離を最大
                if (CurrX >= 0) CurrX++;
                else if (CurrX < 0) CurrX--;
            }
            if (T == 2) { //原点からの距離を最小
                if (CurrX > 0) CurrX--;
                else if (CurrX < 0) CurrX++;
                else if (CurrY > 0) CurrY--;
                else if (CurrY < 0) CurrY++;
                else CurrX++;
            }
        }
        Console.WriteLine(Math.Abs(CurrX) + Math.Abs(CurrY));
    }
}

解説

?の数をカウントして、原点からの距離が最小または最大となるように移動してます。

ベクトルの加算は交換法則が成立するので、?は後回しでも問題ありません。