AOJ 0534 連鎖

問題へのリンク

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

    static List<char> mColorList = new List<char>();
    static int UB;

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

        int CurrInd = 0;
        while (true) {
            int N = int.Parse(InputList[CurrInd]);
            if (N == 0) break;

            mColorList.Clear();
            for (int I = CurrInd + 1; I <= CurrInd + 1 + N - 1; I++) {
                int CurrColor = int.Parse(InputList[I]);

                if (CurrColor == 1) mColorList.Add('R');
                if (CurrColor == 2) mColorList.Add('B');
                if (CurrColor == 3) mColorList.Add('Y');
            }
            int Result = Solve();
            Console.WriteLine(Result);

            CurrInd += 1 + N;
        }
    }

    static int Solve()
    {
        UB = mColorList.Count - 1;

        var DeleteCntList = new List<int>();
        DeleteCntList.Add(0);

        for (int I = 0; I <= UB; I++) {
            // 左右の少なくとも片方と色が違うこと
            bool IsOK1 = false;
            bool IsOK2 = false;
            if (0 < I && mColorList[I] != mColorList[I - 1]) IsOK1 = true;
            if (I < UB && mColorList[I] != mColorList[I + 1]) IsOK2 = true;

            if (IsOK1 == false && IsOK2 == false) continue;

            foreach (char EachColor in new char[] { 'R', 'B', 'Y' }) {
                if (EachColor == mColorList[I]) continue;

                bool IsDeleted;
                int DeleteRangeSta;
                int DeleteRangeEnd;

                ExecDelete(I, EachColor, out IsDeleted, out DeleteRangeSta, out DeleteRangeEnd);
                if (IsDeleted == false) continue;

                DeleteCntList.Add(DeleteRangeEnd - DeleteRangeSta + 1);

                while (true) {
                    if (DeleteRangeSta == 0) break;
                    if (DeleteRangeEnd == UB) break;

                    char ColorLeft = mColorList[DeleteRangeSta - 1];
                    char ColorRight = mColorList[DeleteRangeEnd + 1];

                    if (ColorLeft != ColorRight) break;

                    int NewLeft = CheckSameColor(DeleteRangeSta - 1, -1);
                    int NewRight = CheckSameColor(DeleteRangeEnd + 1, +1);

                    int SameColorCnt = 0;
                    SameColorCnt += Math.Abs(DeleteRangeSta - NewLeft);
                    SameColorCnt += Math.Abs(DeleteRangeEnd - NewRight);

                    if (SameColorCnt <= 3) break;

                    DeleteRangeSta = NewLeft;
                    DeleteRangeEnd = NewRight;
                    DeleteCntList.Add(DeleteRangeEnd - DeleteRangeSta + 1);
                }
            }
        }

        int MaxDeleteCnt = DeleteCntList.Max();
        return mColorList.Count - MaxDeleteCnt;
    }

    // 変更ind,変更Colorを引数として、
    // 削除可否,削除区間Sta,削除区間Endを返す
    static void ExecDelete(int pInd, char pColor,
        out bool pIsDeleted, out int pDeleteRangeSta, out int pDeleteRangeEnd)
    {
        pIsDeleted = false;
        pDeleteRangeSta = pDeleteRangeEnd = pInd;

        // 左と色が同じ場合
        if (pInd > 0) {
            if (mColorList[pInd - 1] == pColor) {
                int ResultInd = CheckSameColor(pInd - 1, -1);
                pDeleteRangeSta = ResultInd;
            }
        }

        // 右と色が同じ場合
        if (pInd < UB) {
            if (mColorList[pInd + 1] == pColor) {
                int ResultInd = CheckSameColor(pInd + 1, +1);
                pDeleteRangeEnd = ResultInd;
            }
        }

        int SameColorRange = pDeleteRangeEnd - pDeleteRangeSta + 1;
        pIsDeleted = (SameColorRange >= 4);
    }

    // Indとベクトルを引数とし、どこまで同じ色かを返す
    static int CheckSameColor(int pInd, int pVect)
    {
        int CurrInd = pInd;
        char CurrColor = mColorList[CurrInd];

        while (true) {
            int NextInd = CurrInd + pVect;
            if (NextInd < 0 || UB < NextInd) break;

            if (mColorList[NextInd] != CurrColor) break;

            CurrInd = NextInd;
        }
        return CurrInd;
    }
}

解説

色の変更を全てシュミレーションしてます。