ABC236-E Average and 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("6");
            WillReturn.Add("2 1 2 1 1 10");
            //4
            //2
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("7");
            WillReturn.Add("3 1 4 1 5 9 2");
            //5.250000000
            //4
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static long[] mAArr;
    static long UB;

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

        decimal AVGMax = DeriveAvgMax();
        Console.WriteLine(AVGMax);

        long MedianMax = DeriveMedianMax();
        Console.WriteLine(MedianMax);
    }

    // 平均の最大値を求める
    static decimal DeriveAvgMax()
    {
        decimal L = 0;
        decimal R = mAArr.Max();

        if (CanAchieveAVG(R)) {
            return R;
        }

        while (L + 0.00000001M < R) {
            decimal Mid = (L + R) / 2;
            if (CanAchieveAVG(Mid)) {
                L = Mid;
            }
            else {
                R = Mid;
            }
        }
        return L;
    }

    // 平均をX以上にできるかを判定
    static bool CanAchieveAVG(decimal pX)
    {
        // Max(シグマ(値 - X)) [現在Ind] なDP表
        decimal?[] DPArr = new decimal?[UB + 1];
        DPArr[0] = mAArr[0] - pX;
        DPArr[1] = mAArr[1] - pX;

        // 配るDP
        for (long I = 0; I <= UB; I++) {
            Action<long> UpdateAct = (pNewInd) =>
            {
                if (pNewInd > UB) return;
                decimal NewVal = DPArr[I].Value + mAArr[pNewInd] - pX;
                if (DPArr[pNewInd].HasValue) {
                    if (DPArr[pNewInd] >= NewVal) {
                        return;
                    }
                }
                DPArr[pNewInd] = NewVal;
            };
            UpdateAct(I + 1);
            UpdateAct(I + 2);
        }

        if (DPArr[UB].Value >= 0) return true;
        if (DPArr[UB - 1].Value >= 0) return true;
        return false;
    }

    // 中央値の最大値を求める
    static long DeriveMedianMax()
    {
        long L = 0;
        long R = mAArr.Max();

        if (CanAchieveMedian(R)) {
            return R;
        }

        while (L + 1 < R) {
            long Mid = (L + R) / 2;
            if (CanAchieveMedian(Mid)) {
                L = Mid;
            }
            else {
                R = Mid;
            }
        }
        return L;
    }

    // 中央値をX以上にできるかを判定
    static bool CanAchieveMedian(long pX)
    {
        // 中央値との大小関係で、+1か-1に変換
        long[] ChangedValArr = new long[UB + 1];
        for (long I = 0; I <= UB; I++) {
            if (mAArr[I] >= pX) {
                ChangedValArr[I] = 1;
            }
            else {
                ChangedValArr[I] = -1;
            }
        }

        // Max(シグマ(値)) [現在Ind] なDP表
        long?[] DPArr = new long?[UB + 1];
        DPArr[0] = ChangedValArr[0];
        DPArr[1] = ChangedValArr[1];

        // 配るDP
        for (long I = 0; I <= UB; I++) {
            Action<long> UpdateAct = (pNewInd) =>
            {
                if (pNewInd > UB) return;
                long NewVal = DPArr[I].Value + ChangedValArr[pNewInd];
                if (DPArr[pNewInd].HasValue) {
                    if (DPArr[pNewInd] >= NewVal) {
                        return;
                    }
                }
                DPArr[pNewInd] = NewVal;
            };
            UpdateAct(I + 1);
            UpdateAct(I + 2);
        }

        if (DPArr[UB].Value >= 1) return true;
        if (DPArr[UB - 1].Value >= 1) return true;
        return false;
    }
}

解説

平均は、
シグマ(値) / 個数 ですが
シグマ(値) / シグマ(1)
と考えることができます。

平均をX以上にできるかという不等式は、
シグマ(値) / シグマ(1) >= X
で変形すると
シグマ(値) >= シグマ(X)
シグマ(値 - X) >= 0
で、

Max(シグマ(値 - X)) [現在Ind] なDP表
を更新するDPを、二分法のCanAchieveメソッドで行うことができます。

中央値に関しては、
中央値以上の値を+1
中央値未満の値を-1
として、同様のDPを、二分法のCanAchieveメソッドで行うことができます。