square869120コンテスト6 B問題 AtCoder Market

問題へのリンク

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("5 7");
            WillReturn.Add("2 6");
            WillReturn.Add("8 10");
            //18
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("5");
            WillReturn.Add("1 71");
            WillReturn.Add("43 64");
            WillReturn.Add("13 35");
            WillReturn.Add("14 54");
            WillReturn.Add("79 85");
            //334
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("11");
            WillReturn.Add("15004200 341668840");
            WillReturn.Add("277786703 825590503");
            WillReturn.Add("85505967 410375631");
            WillReturn.Add("797368845 930277710");
            WillReturn.Add("90107929 763195990");
            WillReturn.Add("104844373 888031128");
            WillReturn.Add("338351523 715240891");
            WillReturn.Add("458782074 493862093");
            WillReturn.Add("189601059 534714600");
            WillReturn.Add("299073643 971113974");
            WillReturn.Add("98291394 443377420");
            //8494550716
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    struct ABInfoDef
    {
        internal long A;
        internal long B;
    }
    static List<ABInfoDef> mABInfoList = new List<ABInfoDef>();

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

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

        foreach (string EachStr in InputList.Skip(1)) {
            SplitAct(EachStr);
            ABInfoDef WillAdd;
            WillAdd.A = wkArr[0];
            WillAdd.B = wkArr[1];
            mABInfoList.Add(WillAdd);
        }

        long MinVal1 = ExecSanbuntansaku(mABInfoList.Select(px => px.A).ToArray());
        long MinVal2 = ExecSanbuntansaku(mABInfoList.Select(px => px.B).ToArray());

        long Answer = 0;
        foreach (ABInfoDef EachABInfo in mABInfoList) {
            Answer += Math.Abs(MinVal1 - EachABInfo.A);
            Answer += Math.Abs(EachABInfo.B - EachABInfo.A);
            Answer += Math.Abs(MinVal2 - EachABInfo.B);
        }
        Console.WriteLine(Answer);
    }

    // 三分探索で、差が一番小さくなる座標を返す
    static long ExecSanbuntansaku(long[] pArr)
    {
        long L = pArr.Min();
        long R = pArr.Max();

        // Valを引数として、関数値を返す
        Func<long, long> CalcFunc = pVal =>
        {
            return pArr.Sum(pX => Math.Abs(pX - pVal));
        };

        var PairHashSet = new HashSet<string>();
        while (L + 1 < R) {
            long C1 = (L * 2 + R) / 3;
            long C2 = (L + R * 2) / 3;

            long C1Val = CalcFunc(C1);
            long C2Val = CalcFunc(C2);

            if (C1Val < C2Val) {
                R = C2;
            }
            else {
                L = C1;
            }

            string Hash = string.Format("{0},{1}", L, R);
            if (PairHashSet.Add(Hash) == false) {
                break;
            }
        }

        long MinVal = long.MaxValue;
        long MinInd = -1;
        for (long I = L; I <= R; I++) {
            long CurrVal = CalcFunc(I);
            if (MinVal > CurrVal) {
                MinVal = CurrVal;
                MinInd = I;
            }
        }
        return MinInd;
    }
}

解説

最適な入口と
最適な出口は、
三分探索で求めることができます。