ABC399-D Switch Seats

問題へのリンク

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("3");
            WillReturn.Add("3");
            WillReturn.Add("1 2 3 3 1 2");
            WillReturn.Add("4");
            WillReturn.Add("1 1 2 2 3 3 4 4");
            WillReturn.Add("5");
            WillReturn.Add("1 2 3 4 5 1 2 3 4 5");
            //1
            //0
            //4
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

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

        var sb = new System.Text.StringBuilder();
        for (int I = 2; I <= InputList.Count - 1; I += 2) {
            mAArr = InputList[I].Split(' ').Select(pX => long.Parse(pX)).ToArray();
            long Answer = Solve();
            sb.Append(Answer);
            sb.AppendLine();
        }
        Console.Write(sb.ToString());
    }

    static long[] mAArr;
    static long UB;

    static Dictionary<long, List<long>> mIndListDict = new Dictionary<long, List<long>>();
    static HashSet<long> mNGValSet = new HashSet<long>();

    static long Solve()
    {
        UB = mAArr.GetUpperBound(0);

        mIndListDict.Clear();
        mNGValSet.Clear();

        var AnswerSet = new HashSet<string>();
        for (long I = 0; I <= UB; I++) {
            long CurrVal = mAArr[I];
            if (I < UB) {
                if (CurrVal == mAArr[I + 1]) {
                    mNGValSet.Add(CurrVal);
                }
            }
        }

        for (long I = 0; I <= UB; I++) {
            long CurrVal = mAArr[I];
            if (mIndListDict.ContainsKey(CurrVal) == false) {
                mIndListDict[CurrVal] = new List<long>();
            }
            mIndListDict[CurrVal].Add(I);
        }

        for (long I = 0; I <= UB; I++) {
            long CurrVal = mAArr[I];
            if (mNGValSet.Contains(CurrVal)) continue;

            long Ind1 = mIndListDict[CurrVal][0];
            long Ind2 = mIndListDict[CurrVal][1];
            if (I != Ind1) continue;

            var ValSet1 = TonariValSet(Ind1);
            var ValSet2 = TonariValSet(Ind2);
            ValSet1.Remove(CurrVal);
            ValSet2.Remove(CurrVal);

            foreach (long EachVal in ValSet1) {
                if (ValSet2.Contains(EachVal) == false) continue;

                List<long> IndList = mIndListDict[EachVal];
                bool IsOK = true;
                foreach (long EachInd in IndList) {
                    if (Math.Abs(EachInd - Ind1) == 1) continue;
                    if (Math.Abs(EachInd - Ind2) == 1) continue;
                    IsOK = false;
                }
                if (IsOK) {
                    AnswerSet.Add(AnswerHash(CurrVal, EachVal));
                }
            }
        }
        return AnswerSet.Count;
    }

    // カップルのペアを正規化したハッシュ値を返す
    static string AnswerHash(long pVal1, long pVal2)
    {
        long Min = Math.Min(pVal1, pVal2);
        long Max = Math.Max(pVal1, pVal2);
        return string.Format("{0},{1}", Min, Max);
    }

    // Indを引数として、左右の値のSetを返す
    static HashSet<long> TonariValSet(long pInd)
    {
        var WillReturn = new HashSet<long>();

        long Ind1 = pInd - 1;
        long Ind2 = pInd + 1;

        if (0 <= Ind1 && Ind1 <= UB) {
            if (mNGValSet.Contains(mAArr[Ind1]) == false) {
                WillReturn.Add(mAArr[Ind1]);
            }
        }
        if (0 <= Ind2 && Ind2 <= UB) {
            if (mNGValSet.Contains(mAArr[Ind2]) == false) {
                WillReturn.Add(mAArr[Ind2]);
            }
        }
        return WillReturn;
    }
}

解説

ダイソーのマグネット付数字で考察すると

IndのList[値]なDictを用意し、
順にチェックすれば良いと分かります。