AtCoderのABC
次のABCの問題へ
前のABCの問題へ
ABC484-D Move One Card Left
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");
//12
}
else if (InputPattern == "Input2") {
WillReturn.Add("5");
WillReturn.Add("1 1 1 1 1");
//1
}
else if (InputPattern == "Input3") {
WillReturn.Add("30");
WillReturn.Add("24 22 18 20 14 22 14 14 26 14 26 26 20 22 24 18 22 22 14 24 18 14 14 24 22 18 18 26 14 20");
//303
}
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 UB = AArr.GetUpperBound(0);
// 〇の個数[右の値]なDict
var CntDict = new Dictionary<long, long>();
long AllCnt = 0;
long Answer = 0;
foreach (long EachA in AArr) {
CntDict[EachA] = 0;
}
for (long I = 0; I <= UB; I++) {
if (I == UB || AArr[I] != AArr[I + 1]) {
long CanMoveCnt = AllCnt - CntDict[AArr[I]];
//Console.WriteLine("Ind={0},A={1}は、{2}箇所に移動可", I, AArr[I], CanMoveCnt);
Answer += CanMoveCnt;
}
else {
//Console.WriteLine("Ind={0},A={1}は移動不可", I, AArr[I]);
}
AllCnt++;
CntDict[AArr[I]]++;
}
Console.WriteLine(Answer + 1);
}
}
解説
まず、ダイソーのオセロセットで2色だけの世界で考えます。
黒黒白黒白白黒白白白白
左に余白を用意し、余白に移動すると考えます。
○黒○黒○白○黒○白○白○黒○白○白○白○白
移動後の文字列は重複を除外して、何通りあるかを考える必要がありますが、
これは、元の文字列と上下に並べて比較した時に、
右から見て最初に差異がある位置(Xとおきます)と、[0,X]の文字配置のペアで
一意になるようにし、重複を防いで考えることができます。
左からオセロの石を順に見ていき、区別できる移動が何通りあるかを考えます。
1 2 3 4 5 6 7 8 9 A B
○黒○黒○白○黒○白○白○黒○白○白○白○白
7の黒は、右が黒でない○に移動可能だと分かります。
Bの白は、右が白でない○に移動可能だと分かります。
また、
56の白は、一番右にある6の白のみが移動可能だと分かります。
89ABの白は、一番右にあるBの白のみが移動可能だと分かります。
以上の考察により、右にある値ごとの○の数を、Dictionaryで管理しつつ、
移動可能な石のみを移動させていき、解を求めることができます。