第20回PAST M 結合の中央値

問題へのリンク

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");
            WillReturn.Add("1 23 45");
            //231
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("3");
            WillReturn.Add("2 2 4");
            //24
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("2");
            WillReturn.Add("100000000 100000000");
            //100000000100000000
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static long[] GetSplitArr(string pStr)
    {
        return (pStr == "" ? new string[0] : pStr.Split(' ')).Select(pX => long.Parse(pX)).ToArray();
    }

    static long[] mAArr;
    static long mAArr_UB;
    static long mMedianRn;

    static long[] mBeki10Arr;

    static void Main()
    {
        mBeki10Arr = GetBekiArr(10);

        List<string> InputList = GetInputList();
        mAArr = GetSplitArr(InputList[1]);
        Array.Sort(mAArr);
        mAArr_UB = mAArr.GetUpperBound(0);

        long ArrLen = mAArr.Length;
        long TotalCnt = ArrLen * (ArrLen - 1);
        mMedianRn = TotalCnt / 2;

        long L = 0;
        long R = CalcFunc(mAArr[mAArr_UB], mAArr[mAArr_UB]);

        while (L + 1 < R) {
            long Mid = (L + R) / 2;

            if (CanAchieve(Mid)) {
                R = Mid;
            }
            else {
                L = Mid;
            }
        }
        Console.WriteLine(R);
    }

    // 仮の中央値以下な関数値の個数が、mNeedCnt以上かを返す
    static bool CanAchieve(long pKariMedian)
    {
        long TotalCnt = 0;
        foreach (long EachA in mAArr) {
            long ResultInd = ExecNibunhou_LowerOrEqual_Max(pKariMedian, EachA, mAArr);
            if (ResultInd == -1) continue;

            long CurrCnt = ResultInd + 1;
            long CurrVal = CalcFunc(EachA, EachA);
            if (CurrVal <= pKariMedian) {
                CurrCnt--;
            }

            TotalCnt += CurrCnt;
            if (TotalCnt >= mMedianRn) {
                return true;
            }
        }
        return TotalCnt >= mMedianRn;
    }

    // 二分法で、閾値以下で最大の値を持つ、添字を返す
    static long ExecNibunhou_LowerOrEqual_Max(long pShikii, long pBaseVal, long[] pArr)
    {
        if (pArr.Length == 0) return -1;

        // 最後の要素が閾値以下の特殊ケース
        if (pShikii >= CalcFunc(pArr[mAArr_UB], pBaseVal)) {
            return pArr.GetUpperBound(0);
        }
        // 最初の要素が閾値超えの特殊ケース
        if (pShikii < CalcFunc(pArr[0], pBaseVal)) {
            return -1;
        }

        long L = 0;
        long R = mAArr_UB;

        while (L + 1 < R) {
            long Mid = (L + R) / 2;

            if (CalcFunc(pArr[Mid], pBaseVal) <= pShikii) {
                L = Mid;
            }
            else {
                R = Mid;
            }
        }
        return L;
    }

    // f(A,B)の結果を返す
    static long CalcFunc(long pA, long pB)
    {
        long pKeta = GetLongKeta(pB);
        long Result = pA * mBeki10Arr[pKeta] + pB;
        return Result;
    }

    ////////////////////////////////////////////////////////////////
    // long型の桁数を返す
    ////////////////////////////////////////////////////////////////
    static long GetLongKeta(long pVal)
    {
        if (pVal <= 9) return 1;
        if (pVal <= 99) return 2;
        if (pVal <= 999) return 3;
        if (pVal <= 9999) return 4;
        if (pVal <= 99999) return 5;
        if (pVal <= 999999) return 6;
        if (pVal <= 9999999) return 7;
        if (pVal <= 99999999) return 8;
        if (pVal <= 999999999) return 9;
        if (pVal <= 9999999999) return 10;
        if (pVal <= 99999999999) return 11;
        if (pVal <= 999999999999) return 12;
        if (pVal <= 9999999999999) return 13;
        if (pVal <= 99999999999999) return 14;
        if (pVal <= 999999999999999) return 15;
        if (pVal <= 9999999999999999) return 16;
        if (pVal <= 99999999999999999) return 17;
        if (pVal <= 999999999999999999) return 18;
        return 19;
    }

    ////////////////////////////////////////////////////////////////
    // べき数の配列を返す。
    // 例 2を引数にして呼ぶと
    // BekiArr[0]= 1
    // BekiArr[1]= 2
    // BekiArr[2]= 4
    // BekiArr[3]= 8
    // BekiArr[4]=16
    // という配列を返す。
    //
    // 使用手順1 グローバルで定義
    // static long[] mBeki2Arr;
    // static long[] mBeki10Arr;
    //
    // 使用手順2 Mainメソッドで呼ぶ
    // mBeki2Arr = GetBekiArr(2);
    // mBeki10Arr = GetBekiArr(10);
    ////////////////////////////////////////////////////////////////
    static long[] GetBekiArr(long pVal)
    {
        // long型の2正数の掛け算が、Limitを超えるかを返す
        Func<long, long, long, bool> WillOverProdFunc = (pA, pB, pLimit) =>
        {
            return pA > pLimit / pB;
        };

        var BekiDict = new Dictionary<long, long>();
        long CurrBeki = 1;
        long CurrShisuu = 0;
        while (true) {
            BekiDict[CurrShisuu] = CurrBeki;

            if (WillOverProdFunc(CurrBeki, pVal, long.MaxValue)) break;
            CurrBeki *= pVal;
            CurrShisuu++;
        }

        return BekiDict.Values.ToArray();
    }
}

解説

中央値がK番目とすると、

仮の中央値を決め、
仮の中央値以下の値の個数がK個未満と
仮の中央値以下の値の個数がK個以上の境界を調べれば
中央値が分かります。

二分探索のイメージ
K個未満 | K個以上
-----------------
L       |       R

さらに二分探索の中で、
ExecNibunhou_LowerOrEqual_Maxによる二分探索も使用してます。