AtCoderのABC    次のABCの問題へ    前のABCの問題へ

ABC484-C Move One Card


問題へのリンク


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("6");
            WillReturn.Add("1 4 1 4 2 1");
            WillReturn.Add("1 4 1 1 4 2");
            //Yes
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("2");
            WillReturn.Add("1 1");
            WillReturn.Add("1 2");
            //No
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("3");
            WillReturn.Add("1 2 3");
            WillReturn.Add("1 2 3");
            //Yes
        }
        else if (InputPattern == "Input4") {
            WillReturn.Add("30");
            WillReturn.Add("25 11 21 15 30 20 17 19 17 21 10 13 22 10 22 14 30 25 17 25 11 19 27 27 15 18 16 16 20 16");
            WillReturn.Add("25 11 15 30 20 17 19 17 21 10 13 22 10 22 14 30 25 17 25 11 19 27 27 15 21 18 16 16 20 16");
            //Yes
        }
        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();
    }

    static void Main()
    {
        List<string> InputList = GetInputList();
        long[] AArr = GetSplitArr(InputList[1]);
        long[] BArr = GetSplitArr(InputList[2]);
        long UB = AArr.GetUpperBound(0);

        // 十分条件のチェック
        if (AArr.SequenceEqual(BArr)) {
            Console.WriteLine("Yes");
            return;
        }

        var UnMatchIndList = new List<int>();
        for (int I = 0; I <= UB; I++) {
            if (AArr[I] != BArr[I]) {
                UnMatchIndList.Add(I);
            }
        }
        int RangeSta = UnMatchIndList.Min();
        int RangeEnd = UnMatchIndList.Max();

        long[] NewAArr1 = new long[AArr.Length];
        long[] NewAArr2 = new long[AArr.Length];

        for (int I = 0; I <= UB; I++) {
            if (RangeSta <= I && I <= RangeEnd) {
                int Target = I + 1;
                if (Target > RangeEnd) {
                    Target = RangeSta;
                }
                NewAArr1[Target] = AArr[I];

                Target = I - 1;
                if (Target < RangeSta) {
                    Target = RangeEnd;
                }
                NewAArr2[Target] = AArr[I];
            }
            else {
                NewAArr1[I] = AArr[I];
                NewAArr2[I] = AArr[I];
            }
        }

        if (NewAArr1.SequenceEqual(BArr) || NewAArr2.SequenceEqual(BArr)) {
            Console.WriteLine("Yes");
            return;
        }
        Console.WriteLine("No");
    }
}


解説

まず十分条件として、最初から一致してるなら
Yesです。

図を書いて考えます。
上下で一致なら○
上下で不一致なら×
で表現します。

○○○○×○×××○×○○×○○

アンマッチな箇所は、変更するのが必要条件です。

また、配列のある要素を任意の場所に挿入するのは、
結局は、区間を決めての
1つ左への回転シフトか
1つ右への回転シフトの
どちらかです。

以上の考察により、
一番左の×と
一番右の×を求め、
1つ左への回転シフトと
1つ右への回転シフトの2つを試し、
十分性の確認をすれば良いです。