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で管理しつつ、
移動可能な石のみを移動させていき、解を求めることができます。