ABC212-C Min Difference

問題へのリンク

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 2");
            WillReturn.Add("1 6");
            WillReturn.Add("4 9");
            //2
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("1 1");
            WillReturn.Add("10");
            WillReturn.Add("10");
            //0
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("6 8");
            WillReturn.Add("82 76 82 82 71 70");
            WillReturn.Add("17 39 67 2 45 35 22 24");
            //3
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static long[] mAArr;
    static long[] mBArr;

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

        Array.Sort(mAArr);
        Array.Sort(mBArr);

        long Answer = long.MaxValue;
        foreach (long EachA in mAArr) {
            long AnswerKouho = ExecSanbuntansaku(EachA);
            Answer = Math.Min(Answer, AnswerKouho);
        }
        Console.WriteLine(Answer);
    }

    // 三分探索で極小値を求める
    static long ExecSanbuntansaku(long pAVal)
    {
        long L = 0;
        long R = mBArr.GetUpperBound(0);

        // Indを引数として、関数値を返す
        Func<long, long> CalcFunc = pInd =>
        {
            return Math.Abs(pAVal - mBArr[pInd]);
        };

        var PairHashSet = new HashSet<long>();
        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;
            }

            long Hash = L * 1000000 + R;
            if (PairHashSet.Add(Hash) == false) {
                break;
            }
        }

        var MinKouhoList = new List<long>();
        for (long I = L; I <= R; I++) {
            MinKouhoList.Add(CalcFunc(I));
        }
        return MinKouhoList.Min();
    }
}

解説

配列Aを全探索し、Aの要素ごとに
配列Bを、三分探索してます。

別解として、AとBを混ぜて昇順にソートした際に
隣接したAとBであることが解であることの必要条件と考えて
隣接したAとBの差を全て調べる方法もあります。