yukicoder 3017 交互浴

問題へのリンク

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

    static void Main()
    {
        List<string> InputList = GetInputList();
        long[] HArr = InputList[1].Split(' ').Select(pX => long.Parse(pX)).ToArray();

        var InsLinkedList = new LinkedList<RunLenInfo>();
        var InitJyoutai = new RunLenInfo();
        InitJyoutai.Len = 1000000000000000000;
        InitJyoutai.Color = '緑';
        InsLinkedList.AddFirst(InitJyoutai);

        long WaterLen = 0;
        for (long I = 0; I <= HArr.GetUpperBound(0); I++) {
            var CurrJyoutai = new RunLenInfo();
            CurrJyoutai.Len = HArr[I];
            CurrJyoutai.Color = '緑';
            if (I % 2 == 0) {
                CurrJyoutai.Color = '水';
            }

            long RestRemoveLen = HArr[I];
            while (true) {
                RunLenInfo TopItem = InsLinkedList.First.Value;

                long CurrRemoveLen = Math.Min(RestRemoveLen, TopItem.Len);
                TopItem.Len -= CurrRemoveLen;
                RestRemoveLen -= CurrRemoveLen;

                if (TopItem.Color == '水') {
                    WaterLen -= CurrRemoveLen;
                }
                if (TopItem.Len == 0) {
                    InsLinkedList.RemoveFirst();
                }

                if (RestRemoveLen == 0) {
                    break;
                }
            }

            InsLinkedList.AddFirst(CurrJyoutai);
            if (CurrJyoutai.Color == '水') {
                WaterLen += CurrJyoutai.Len;
            }
            Console.WriteLine(WaterLen);
        }
    }

    class RunLenInfo
    {
        internal long Len;
        internal char Color;
    }
}

解説

ランレングス圧縮した結果をLinkedListで扱ってます。