ABC421-D RLE Moving

問題へのリンク

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("0 0 4 2");
            WillReturn.Add("3 2 1");
            WillReturn.Add("R 2");
            WillReturn.Add("D 1");
            WillReturn.Add("U 3");
            //1
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("1000000000 1000000000 -1000000000 -1000000000");
            WillReturn.Add("3000000000 3 3");
            WillReturn.Add("L 1000000000");
            WillReturn.Add("U 1000000000");
            WillReturn.Add("U 1000000000");
            WillReturn.Add("D 1000000000");
            WillReturn.Add("R 1000000000");
            WillReturn.Add("U 1000000000");
            //1000000001
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("3 3 3 2");
            WillReturn.Add("1 1 1");
            WillReturn.Add("L 1");
            WillReturn.Add("R 1");
            //0
        }
        else if (InputPattern == "Input4") {
            WillReturn.Add("0 0 0 0");
            WillReturn.Add("1 1 1");
            WillReturn.Add("L 1");
            WillReturn.Add("R 1");
            //0
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static long[] GetSplitArr(string pStr)
    {
        return (pStr == "" ? new string[0] : pStr.Split(' ')).Select(pX => long.Parse(pX)).ToArray();
    }

    class MoveInfoDef
    {
        internal long VectX;
        internal long VectY;
        internal long Length;
    }

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

        long[] wkArr = { };
        Action<string> SplitAct = (pStr) => wkArr = GetSplitArr(pStr);

        SplitAct(InputList[0]);
        long T_X = wkArr[1];
        long T_Y = wkArr[0];

        long A_X = wkArr[3];
        long A_Y = wkArr[2];

        SplitAct(InputList[1]);
        long M = wkArr[1];

        var QueTaka = new Queue<MoveInfoDef>();

        foreach (string EachStr in InputList.Skip(2).Take((int)M)) {
            string[] SplitArr = EachStr.Split(' ');
            string Vect = SplitArr[0];
            long Length = long.Parse(SplitArr[1]);

            var WillEnqueue = new MoveInfoDef();
            WillEnqueue.VectX = 0;
            WillEnqueue.VectY = 0;
            if (Vect == "U") WillEnqueue.VectY = -1;
            if (Vect == "D") WillEnqueue.VectY = +1;
            if (Vect == "R") WillEnqueue.VectX = +1;
            if (Vect == "L") WillEnqueue.VectX = -1;
            WillEnqueue.Length = Length;
            QueTaka.Enqueue(WillEnqueue);
        }

        var QueAoki = new Queue<MoveInfoDef>();

        foreach (string EachStr in InputList.Skip(2 + (int)M)) {
            string[] SplitArr = EachStr.Split(' ');
            string Vect = SplitArr[0];
            long Length = long.Parse(SplitArr[1]);

            var WillEnqueue = new MoveInfoDef();
            WillEnqueue.VectX = 0;
            WillEnqueue.VectY = 0;
            if (Vect == "U") WillEnqueue.VectY = -1;
            if (Vect == "D") WillEnqueue.VectY = +1;
            if (Vect == "R") WillEnqueue.VectX = +1;
            if (Vect == "L") WillEnqueue.VectX = -1;
            WillEnqueue.Length = Length;
            QueAoki.Enqueue(WillEnqueue);
        }

        long Answer = 0;
        while (QueTaka.Count > 0 && QueAoki.Count > 0) {
            MoveInfoDef PeekedTaka = QueTaka.Peek();
            MoveInfoDef PeekedAoki = QueAoki.Peek();

            long MinLength = Math.Min(PeekedTaka.Length, PeekedAoki.Length);

            // 一緒に移動する場合
            bool IsSameMove = false;
            if (T_X == A_X && T_Y == A_Y) {
                if (PeekedTaka.VectX == PeekedAoki.VectX && PeekedTaka.VectY == PeekedAoki.VectY) {
                    Answer += MinLength;
                    IsSameMove = true;
                }
            }

            if (IsSameMove == false) {
                long Kyori = Math.Abs(T_X - A_X) + Math.Abs(T_Y - A_Y);

                // マンハッタン距離が偶数で0超えの場合
                if (Kyori % 2 == 0 && Kyori > 0) {
                    MinLength = Math.Min(MinLength, Kyori / 2);
                }
            }

            T_X += PeekedTaka.VectX * MinLength;
            T_Y += PeekedTaka.VectY * MinLength;

            A_X += PeekedAoki.VectX * MinLength;
            A_Y += PeekedAoki.VectY * MinLength;

            PeekedTaka.Length -= MinLength;
            PeekedAoki.Length -= MinLength;

            if (IsSameMove == false) {
                if (T_X == A_X && T_Y == A_Y) {
                    Answer++;
                }
            }

            if (PeekedTaka.Length == 0) QueTaka.Dequeue();
            if (PeekedAoki.Length == 0) QueAoki.Dequeue();
        }

        Console.WriteLine(Answer);
    }
}

解説

変位ベクトルの組み合わせごとに、移動を分けてます。

衝突判定で、マンハッタン距離が偶数で0超えの場合は、
マンハッタン距離の半分での移動を区切るようにしてます。