AOJ 0527 碁石ならべ

問題へのリンク

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

    class RunLenInfoDef
    {
        internal int Color;
        internal int Len;
    }
    static List<RunLenInfoDef> mRunLenInfoList = new List<RunLenInfoDef>();

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

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

            if (N == 0) break;
            var ColorList = new List<int>();
            for (int I = CurrInd + 1; I <= CurrInd + 1 + N - 1; I++) {
                ColorList.Add(int.Parse(InputList[I]));
            }
            Solve(ColorList.ToArray());

            CurrInd += 1 + N;
        }
    }

    static void Solve(int[] pColorArr)
    {
        mRunLenInfoList.Clear();
        for (int I = 0; I <= pColorArr.GetUpperBound(0); I++) {
            int LastInd = mRunLenInfoList.Count - 1;

            // 最初の場合
            if (I == 0) {
                var WillAdd = new RunLenInfoDef();
                WillAdd.Color = pColorArr[I];
                WillAdd.Len = 1;
                mRunLenInfoList.Add(WillAdd);
            }
            // 奇数番目なら変換なし
            else if (I % 2 == 0) {
                if (pColorArr[I] == mRunLenInfoList[LastInd].Color) {
                    mRunLenInfoList[LastInd].Len++;
                }
                else {
                    var WillAdd = new RunLenInfoDef();
                    WillAdd.Color = pColorArr[I];
                    WillAdd.Len = 1;
                    mRunLenInfoList.Add(WillAdd);
                }
            }
            // 偶数番目なら変換あり
            else if (I % 2 == 1) {
                if (pColorArr[I] == mRunLenInfoList[LastInd].Color) {
                    mRunLenInfoList[LastInd].Len++;
                }
                else {
                    mRunLenInfoList[LastInd].Len++;
                    mRunLenInfoList[LastInd].Color++;
                    mRunLenInfoList[LastInd].Color %= 2;

                    if (LastInd - 1 >= 0) {
                        if (mRunLenInfoList[LastInd - 1].Color == mRunLenInfoList[LastInd].Color) {
                            mRunLenInfoList[LastInd - 1].Len += mRunLenInfoList[LastInd].Len;
                            mRunLenInfoList.RemoveAt(LastInd);
                        }
                    }
                }
            }
        }

        int Answer = mRunLenInfoList.Where(pX => pX.Color == 0).Sum(pX => pX.Len);
        Console.WriteLine(Answer);
    }
}

解説

ランレングス圧縮を使ってシュミレーションしてます。