ABC080-D Recording

問題へのリンク

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 2");
            WillReturn.Add("1 7 2");
            WillReturn.Add("7 8 1");
            WillReturn.Add("8 12 1");
            //2
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("3 4");
            WillReturn.Add("1 3 2");
            WillReturn.Add("3 4 4");
            WillReturn.Add("1 4 3");
            //3
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("9 4");
            WillReturn.Add("56 60 4");
            WillReturn.Add("33 37 2");
            WillReturn.Add("89 90 3");
            WillReturn.Add("32 43 1");
            WillReturn.Add("67 68 3");
            WillReturn.Add("49 51 3");
            WillReturn.Add("31 32 3");
            WillReturn.Add("70 71 1");
            WillReturn.Add("11 12 3");
            //2
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    class STCInfoDef
    {
        internal int S;
        internal int T;
        internal int C;
    }

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

            int[] wkArr = { };
            Action<string> SplitAct = pStr =>
                wkArr = pStr.Split(' ').Select(pX => int.Parse(pX)).ToArray();

            var STInfoList = new List<STCInfoDef>();
            foreach (string EachStr in InputList.Skip(1)) {
                SplitAct(EachStr);
                var WillAdd = new STCInfoDef();
                WillAdd.S = wkArr[0];
                WillAdd.T = wkArr[1];
                WillAdd.C = wkArr[2];
                STInfoList.Add(WillAdd);
            }

            // 同じチャンネルで区間が重なっていたら合併する
            STInfoList = STInfoList.OrderBy(pX => pX.C).ThenBy(pX => pX.S).ToList();
            for (int I = STInfoList.Count - 1; 1 <= I; I--) {
                if (STInfoList[I - 1].C == STInfoList[I].C
                 && STInfoList[I - 1].T == STInfoList[I].S) {
                    STInfoList[I - 1].T = STInfoList[I].T;
                    STInfoList.RemoveAt(I);
                }
            }

            // いもす法で解く
            var RunSumDict = new SortedDictionary<decimal, long>();

            foreach (STCInfoDef EachSTCInfo in STInfoList) {
                decimal SKey = EachSTCInfo.S - 0.5M;
                decimal TKey = EachSTCInfo.T;

                if (RunSumDict.ContainsKey(SKey) == false) RunSumDict[SKey] = 0;
                if (RunSumDict.ContainsKey(TKey) == false) RunSumDict[TKey] = 0;

                RunSumDict[SKey]++;
                RunSumDict[TKey]--;
            }

            decimal[] KeysArr = RunSumDict.Keys.ToArray();

            // 累積和を求める
            for (int I = 1; I <= KeysArr.GetUpperBound(0); I++) {
                decimal CurrKey = KeysArr[I];
                decimal PrevKey = KeysArr[I - 1];

                RunSumDict[CurrKey] += RunSumDict[PrevKey];
            }

            Console.WriteLine(RunSumDict.Values.Max());
        }
    }
}

解説

最初に、同じチャンネルで区間が重なっていたら合併してます。
次に、いもす法を使ってます。