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つを試し、
十分性の確認をすれば良いです。