ABC364-D K-th Nearest

問題へのリンク

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("4 3");
            WillReturn.Add("-3 -1 5 6");
            WillReturn.Add("-2 3");
            WillReturn.Add("2 1");
            WillReturn.Add("10 4");
            //7
            //3
            //13
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("2 2");
            WillReturn.Add("0 0");
            WillReturn.Add("0 1");
            WillReturn.Add("0 2");
            //0
            //0
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("10 5");
            WillReturn.Add("-84 -60 -41 -100 8 -8 -52 -62 -61 -76");
            WillReturn.Add("-52 5");
            WillReturn.Add("14 4");
            WillReturn.Add("-2 6");
            WillReturn.Add("46 2");
            WillReturn.Add("26 7");
            //11
            //66
            //59
            //54
            //88
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    struct QueryInfoDef
    {
        internal long BasePos;
        internal long K;
    }
    static List<QueryInfoDef> mQueryInfoList = new List<QueryInfoDef>();

    static long[] mAArr;
    static long UB;

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

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

        foreach (string EachStr in InputList.Skip(2)) {
            SplitAct(EachStr);
            QueryInfoDef WillAdd;
            WillAdd.BasePos = wkArr[0];
            WillAdd.K = wkArr[1];
            mQueryInfoList.Add(WillAdd);
        }

        var sb = new System.Text.StringBuilder();
        foreach (QueryInfoDef EachQuery in mQueryInfoList) {
            long BasePos = EachQuery.BasePos;
            long K = EachQuery.K;

            // 0が達成可能な場合
            if (CanAchieve(BasePos, 0, K)) {
                sb.AppendLine("0");
                continue;
            }

            long L = 0;

            long R = long.MaxValue;
            for (long I = 2; I < long.MaxValue; I *= 2) {
                if (CanAchieve(BasePos, I, K)) {
                    R = I;
                    break;
                }
            }

            while (L + 1 < R) {
                long Mid = (L + R) / 2;
                bool Result = CanAchieve(BasePos, Mid, K);

                if (Result) {
                    R = Mid;
                }
                else {
                    L = Mid;
                }
            }
            sb.Append(R);
            sb.AppendLine();
        }
        Console.Write(sb.ToString());
    }

    // 基準点と半径とKを引数とし、K以上の点があるかを判定
    static bool CanAchieve(long pBasePos, long pR, long pK)
    {
        long ArrRangeValueCnt = GetArrRangeValueCnt.GetCnt(mAArr, pBasePos - pR, pBasePos + pR);
        return ArrRangeValueCnt >= pK;
    }
}

#region GetArrRangeValueCnt
// {昇順にソートされた配列,Min,Max}を引数とし、
// Min以上Max以下な値の個数を返す
internal class GetArrRangeValueCnt
{
    static internal long GetCnt(long[] pSortedArr, long pMinVal, long pMaxVal)
    {
        if (pMinVal > pMaxVal) {
            throw new Exception("pMinVal > pMaxVal");
        }

        int ResultInd1 = ExecNibunhou_LowerBound(pMinVal, pSortedArr);
        int ResultInd2 = ExecNibunhou_LowerOrEqual_Max(pMaxVal, pSortedArr);

        if (ResultInd1 == -1 || ResultInd2 == -1) return 0;
        return ResultInd2 - ResultInd1 + 1;
    }

    // 二分法で、Val以上で最小の値を持つ、添字を返す
    static int ExecNibunhou_LowerBound(long pVal, long[] pArr)
    {
        if (pArr.Length == 0) return -1;

        // 最後の要素がVal未満の特殊ケース
        if (pVal > pArr.Last()) {
            return -1;
        }
        // 最初の要素がVal以上の特殊ケース
        if (pVal <= pArr[0]) {
            return 0;
        }

        int L = 0;
        int R = pArr.GetUpperBound(0);

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

            if (pArr[Mid] >= pVal) {
                R = Mid;
            }
            else {
                L = Mid;
            }
        }
        return R;
    }


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

        // 最後の要素がVal以下の特殊ケース
        if (pVal >= pArr.Last()) {
            return pArr.GetUpperBound(0);
        }
        // 最初の要素がVal超えの特殊ケース
        if (pVal < pArr[0]) {
            return -1;
        }

        int L = 0;
        int R = pArr.GetUpperBound(0);

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

            if (pArr[Mid] <= pVal) {
                L = Mid;
            }
            else {
                R = Mid;
            }
        }
        return L;
    }
}
#endregion

解説

基準点ごとに半径を二分探索してます。