ABC366-E Manhattan Multifocal Ellipse

問題へのリンク

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

    static long mD;

    struct PointDef
    {
        internal long X;
        internal long Y;
    }
    static List<PointDef> mPointList = new List<PointDef>();

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

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

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

        foreach (string EachStr in InputList.Skip(1)) {
            SplitAct(EachStr);
            PointDef WillAdd;
            WillAdd.X = wkArr[0];
            WillAdd.Y = wkArr[1];
            mPointList.Add(WillAdd);
        }

        List<long> DistanceListX = DeriveDistanceList(mPointList.Select(pX => pX.X).ToArray());
        List<long> DistanceListY = DeriveDistanceList(mPointList.Select(pX => pX.Y).ToArray());

        DistanceListX.Sort();
        DistanceListY.Sort();

        long Answer = 0;
        foreach (long EachVal in DistanceListX) {
            long RestVal = mD - EachVal;
            int ResultInd = ExecNibunhou_LowerOrEqual_Max(RestVal, DistanceListY);
            if (ResultInd == -1) continue;
            Answer += ResultInd + 1;
        }
        Console.WriteLine(Answer);
    }

    // 成分の配列を引数とし、距離のListを返す
    static List<long> DeriveDistanceList(long[] pPosArr)
    {
        var WillReturn = new List<long>();

        Array.Sort(pPosArr);
        var InsLinkedList = new LinkedList<long>(pPosArr);

        long LeftCnt = 0;
        long RightCnt = InsLinkedList.Count;

        long StaPos = pPosArr.Min() - mD;
        long EndPos = pPosArr.Max() + mD;

        long DictanceSum = pPosArr.Sum(pX => pX - StaPos);

        for (long I = StaPos; I <= EndPos; I++) {
            WillReturn.Add(DictanceSum);

            while (true) {
                if (InsLinkedList.Count > 0 && InsLinkedList.First.Value == I) {
                    LeftCnt++;
                    RightCnt--;
                    InsLinkedList.RemoveFirst();
                }
                else break;
            }

            DictanceSum -= RightCnt;
            DictanceSum += LeftCnt;
        }

        WillReturn.RemoveAll(pX => pX > mD);
        return WillReturn;
    }

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

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

        int L = 0;
        int R = pList.Count - 1;

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

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

解説

X座標とY座標で独立で考え、
候補となる座標ごとの距離のListを作ってから、
二分探索で組み合わせ数を列挙してます。