第8回PAST G K番目の要素

問題へのリンク

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 4");
            WillReturn.Add("3 2 2");
            WillReturn.Add("2 3 4");
            //6
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("2 10");
            WillReturn.Add("4 1000000000 1000000000");
            WillReturn.Add("6 1000000000 1000000000");
            //6000000000
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("5 10");
            WillReturn.Add("3 1 4");
            WillReturn.Add("1 5 9");
            WillReturn.Add("2 6 5");
            WillReturn.Add("3 5 8");
            WillReturn.Add("9 7 9");
            //16
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    struct SuuretuInfoDef
    {
        internal long Kousuu;
        internal long Syokou;
        internal long Kousa;
        internal long Makkou;
    }
    static List<SuuretuInfoDef> mSuuretuInfoList = new List<SuuretuInfoDef>();

    static long mK;

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

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

        SplitAct(InputList[0]);
        mK = wkArr[1];

        foreach (string EachStr in InputList.Skip(1)) {
            SplitAct(EachStr);
            SuuretuInfoDef WillAdd;
            WillAdd.Kousuu = wkArr[0];
            WillAdd.Syokou = wkArr[1];
            WillAdd.Kousa = wkArr[2];
            WillAdd.Makkou = WillAdd.Syokou + WillAdd.Kousa * (WillAdd.Kousuu - 1);
            mSuuretuInfoList.Add(WillAdd);
        }

        long L = 0;
        long R = mSuuretuInfoList.Max(pX => pX.Makkou);

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

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

        Console.WriteLine(R);
    }

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

        foreach (SuuretuInfoDef EachSuuretuInfo in mSuuretuInfoList) {
            long CurrLowerOrEqualCnt = DeriveLowerOrEqualCnt(pVal, EachSuuretuInfo);
            LowerOrEqualCntSum += CurrLowerOrEqualCnt;
            if (LowerOrEqualCntSum >= mK) return true;
        }
        return LowerOrEqualCntSum >= mK;
    }

    // 二分法で、等差数列のpVal以下の項数を求める
    static long DeriveLowerOrEqualCnt(long pVal, SuuretuInfoDef pSuuretuInfo)
    {
        // 末項がpVal以下の特殊ケース
        if (pSuuretuInfo.Makkou <= pVal) {
            return pSuuretuInfo.Kousuu;
        }
        // 初項がpValより大きい特殊ケース
        if (pSuuretuInfo.Syokou > pVal) {
            return 0;
        }

        long L = 1;
        long R = pSuuretuInfo.Kousuu;

        while (L + 1 < R) {
            long Mid = (L + R) / 2;
            long MidVal = pSuuretuInfo.Syokou + pSuuretuInfo.Kousa * (Mid - 1);

            if (MidVal <= pVal) {
                L = Mid;
            }
            else {
                R = Mid;
            }
        }
        return L;
    }
}

解説

5番目は5位なので、順位で考えることができます。
下記の数列で5位の要素を考えます。

30 30 30 60 60 60 90 90 90
順位が5位または5位より悪い順位であることは、
自分以下の要素数が5以上であることと同値になります。

後は、下記の、値に対する順位の単調性を示す図をふまえて、
二分探索を行うことができ、
5位または5位より悪い順位である、最小の値が解となります。

----------------------------------------------
| 5位より良い順位 | 5位または5位より悪い順位 |
----------------------------------------------
値 ------------------------------------------->

また、交差がプラスの等差数列で、閾値以下の値が何項あるかは、
二分探索で求めることができます。

類題

ARC037-C 億マス計算
ABC155-D Pairs