ABC155-D Pairs

問題へのリンク

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 3 -4 -2");
            //-6
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("10 40");
            WillReturn.Add("5 4 3 2 -1 0 0 0 0 0");
            //6
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("30 413");
            WillReturn.Add("-170202098 -268409015 537203564 983211703 21608710 -443999067 -937727165 -97596546 -372334013 398994917 -972141167 798607104 -949068442 -959948616 37909651 0 886627544 -20098238 0 -948955241 0 -214720580 277222296 -18897162 834475626 0 -425610555 110117526 663621752 0");
            //448283280358331064
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static long mK;
    static long[] mAArr;

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

        mAArr = InputList[1].Split(' ').Select(pX => long.Parse(pX)).ToArray();
        Array.Sort(mAArr);

        long MaxABS = mAArr.Max(pX => Math.Abs(pX));
        long L = MaxABS * MaxABS * (-1);
        long R = MaxABS * MaxABS;

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

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

    // Valを引数として、順位がK位、または、K位より悪いか判定
    static bool IsUpperOrEqual(long pVal)
    {
        // 引数と同じか、良い順位の値の件数
        long LowerOrEqualCntSum = 0;

        for (int I = 0; I <= mAArr.GetUpperBound(0) - 1; I++) {
            long CurrLowerOrEqualCnt = DeriveLowerOrEqualCnt(pVal, I);
            LowerOrEqualCntSum += CurrLowerOrEqualCnt;
            if (LowerOrEqualCntSum >= mK) return true;
        }
        return LowerOrEqualCntSum >= mK;
    }

    // ValとAArrの添字を引数として、積がVal以下になる件数を返す
    static long DeriveLowerOrEqualCnt(long pVal, int pAInd)
    {
        long AVal = mAArr[pAInd];

        int L = pAInd + 1;
        int R = mAArr.GetUpperBound(0);

        // AValが負の場合は、積は、添字に対して、広義単調減少
        if (AVal < 0) {
            // 初項がpVal以下の特殊ケース
            if (mAArr[L] * AVal <= pVal) {
                return mAArr.Length - (pAInd + 1);
            }
            // 末項がpVal超えの特殊ケース
            if (mAArr.Last() * AVal > pVal) {
                return 0;
            }

            while (L + 1 < R) {
                int Mid = (L + R) / 2;
                long MidVal = mAArr[Mid] * AVal;

                if (MidVal > pVal) {
                    L = Mid;
                }
                else {
                    R = Mid;
                }
            }
            return mAArr.GetUpperBound(0) - R + 1;
        }

        // AValが負でない場合は、積は、添字に対して、広義単調増加
        else {
            // 初項がpVal超えの特殊ケース
            if (mAArr[L] * AVal > pVal) {
                return 0;
            }
            // 末項がpVal以下の特殊ケース
            if (mAArr.Last() * AVal <= pVal) {
                return mAArr.Length - (pAInd + 1);
            }

            while (L + 1 < R) {
                int Mid = (L + R) / 2;
                long MidVal = mAArr[Mid] * AVal;

                if (MidVal <= pVal) {
                    L = Mid;
                }
                else {
                    R = Mid;
                }
            }
            return L + 1 - (pAInd + 1);
        }
    }
}

解説

値に対する順位の単調性をふまえて、二分探索してます。

例えば
-5 -4 -3 -2 -1 0 1 2 3 4
で左端とのペアを順に考えていくとして、
左端が、マイナスなら、掛ける数が増えれば、積は広義単調減少
左端が、0以上なら、掛ける数が増えれば、積は広義単調増加
なので、二分法のロジックは左端の符号で、分けるようにしてます。

類題

第8回PAST G K番目の要素
ARC037-C 億マス計算