ABC181-E Transformable Teacher

問題へのリンク

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("5 3");
            WillReturn.Add("1 2 3 4 7");
            WillReturn.Add("1 3 8");
            //3
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("7 7");
            WillReturn.Add("31 60 84 23 16 13 32");
            WillReturn.Add("96 80 73 76 87 57 29");
            //34
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("15 10");
            WillReturn.Add("554 525 541 814 661 279 668 360 382 175 833 783 688 793 736");
            WillReturn.Add("496 732 455 306 189 207 976 73 567 759");
            //239
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

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

        Array.Sort(HArr);
        Array.Sort(WArr);

        // 左からの奇数添字での累積和
        var FromLeftRunSumDict = new Dictionary<long, long>();

        // 右からの奇数添字での累積和
        var FromRightRunSumDict = new Dictionary<long, long>();

        long LeftRunSum = 0;
        for (int I = 1; I <= UB; I += 2) {
            LeftRunSum += Math.Abs(HArr[I] - HArr[I - 1]);
            FromLeftRunSumDict[I] = LeftRunSum;
        }

        long RightRunSum = 0;
        for (int I = UB - 1; 0 <= I; I -= 2) {
            RightRunSum += Math.Abs(HArr[I + 1] - HArr[I]);
            FromRightRunSumDict[I] = RightRunSum;
        }

        // Teacherは偶数添字とのみペアになれる
        long Answer = long.MaxValue;
        for (int I = 0; I <= HArr.GetUpperBound(0); I += 2) {
            long AnswerKouho = 0;
            if (I - 1 >= 0) {
                AnswerKouho += FromLeftRunSumDict[I - 1];
            }
            if (I + 1 <= UB) {
                AnswerKouho += FromRightRunSumDict[I + 1];
            }
            AnswerKouho += ExecSanbuntansaku(HArr[I], WArr);
            Answer = Math.Min(Answer, AnswerKouho);
        }

        Console.WriteLine(Answer);
    }

    // 値を引数として、三分探索で極小値を求める
    static long ExecSanbuntansaku(long pVal, long[] pWArr)
    {
        long L = 0;
        long R = pWArr.GetUpperBound(0);

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

            long C1Val = Math.Abs(pVal - pWArr[C1]);
            long C2Val = Math.Abs(pVal - pWArr[C2]);

            if (C1Val < C2Val) {
                R = C2;
            }
            else {
                L = C1;
            }
            long Hash = L * 1000000 + R;
            if (PairHashSet.Add(Hash) == false) {
                break;
            }
        }

        var MinKouhoList = new List<long>();
        for (long I = L; I <= R; I++) {
            long CVal = Math.Abs(pVal - pWArr[I]);
            MinKouhoList.Add(CVal);
        }
        return MinKouhoList.Min();
    }
}

解説

考察を進めると、
左からの累積和と
右からの累積和を事前にもっておき、

Teacherは、(0オリジンでの)偶数添字の生徒とのみペアになれるので、
ペアごとの最適な身長は、三分探索で求めれば良いと分かります。