ABC169-E Count Median

問題へのリンク

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("2");
            WillReturn.Add("1 2");
            WillReturn.Add("2 3");
            //3
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("3");
            WillReturn.Add("100 100");
            WillReturn.Add("10 10000");
            WillReturn.Add("1 1000000000");
            //9991
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    struct ABInfoDef
    {
        internal decimal A;
        internal decimal B;
    }

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

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

        var ABInfoList = new List<ABInfoDef>();
        foreach (string EachStr in InputList.Skip(1)) {
            SplitAct(EachStr);

            ABInfoDef WillAdd;
            WillAdd.A = wkArr[0];
            WillAdd.B = wkArr[1];
            ABInfoList.Add(WillAdd);
        }

        int Cnt = ABInfoList.Count;

        var MinList = new List<decimal>();
        var MaxList = new List<decimal>();
        foreach (ABInfoDef EachABInfo in ABInfoList) {
            MinList.Add(EachABInfo.A);
            MaxList.Add(EachABInfo.B);
        }

        // 昇順にソートする
        MinList.Sort();
        MaxList.Sort();

        decimal MinMedian;
        decimal MaxMedian;
        if (Cnt % 2 == 0) {
            MinMedian = (MinList[Cnt / 2 - 1] + MinList[Cnt / 2]) / 2;
            MaxMedian = (MaxList[Cnt / 2 - 1] + MaxList[Cnt / 2]) / 2;

            Console.WriteLine((MaxMedian - MinMedian) / 0.5M + 1);
        }
        else {
            MinMedian = (MinList[Cnt / 2]);
            MaxMedian = (MaxList[Cnt / 2]);
            Console.WriteLine((MaxMedian - MinMedian) + 1);
        }
    }
}

解説

オセロセットで考察すると、

要素数が奇数の場合は、
中央値は最小の中央値から最大の中央値までを
1刻みで全て作成可能

要素数が偶数の場合は、
中央値は最小の中央値から最大の中央値までを
0.5刻みで全て作成可能

と分かります。