典型90問 007 CP Classes（★3）

問題へのリンク

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("4");
            WillReturn.Add("4000 4400 5000 3200");
            WillReturn.Add("3");
            WillReturn.Add("3312");
            WillReturn.Add("2992");
            WillReturn.Add("4229");
            //112
            //208
            //171
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("1");
            WillReturn.Add("4000");
            WillReturn.Add("10");
            WillReturn.Add("3582");
            WillReturn.Add("3538");
            WillReturn.Add("3320");
            WillReturn.Add("3312");
            WillReturn.Add("3296");
            WillReturn.Add("3257");
            WillReturn.Add("3111");
            WillReturn.Add("3040");
            WillReturn.Add("3013");
            WillReturn.Add("2994");
            //418
            //462
            //680
            //688
            //704
            //743
            //889
            //960
            //987
            //1006
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("10");
            WillReturn.Add("869120000 998244353 777777777 123456789 100100100 464646464 987654321 252525252 869120001 1000000000");
            WillReturn.Add("10");
            WillReturn.Add("4229");
            WillReturn.Add("20210406");
            WillReturn.Add("1");
            WillReturn.Add("268435456");
            WillReturn.Add("3582");
            WillReturn.Add("536870912");
            WillReturn.Add("1000000000");
            WillReturn.Add("869120");
            WillReturn.Add("99999999");
            WillReturn.Add("869120001");
            //100095871
            //79889694
            //100100099
            //15910204
            //100096518
            //72224448
            //0
            //99230980
            //100101
            //0
        }
        else if (InputPattern == "Input4") {
            WillReturn.Add("100");
            WillReturn.Add("298750376 229032640 602876667 944779015 909539868 533609371 231368330 445484152 408704870 850216874 349286798 30417810 807260002 554049450 40706045 380488344 749325840 801881841 459457853 66691229 5235900 8100458 46697277 997429858 827651689 790051948 981897272 271364774 536232393 997361572 449659237 602191750 294800444 346669663 792837293 277667068 997282249 468293808 444906878 702693341 894286137 845317003 27053625 926547765 739689211 447395911 902031510 326127348 582956343 842918193 235655766 844300842 438389323 406413067 862896425 464876303 68833418 76340212 911399808 745744264 551223563 854507876 196296968 52144186 431165823 275217640 424495332 847375861 337078801 83054466 648322745 694789156 301518763 319851750 432518459 772897937 630628124 581390864 313132255 350770227 642944345 677742851 448945480 688009163 160941957 290297295 5532462 823543277 19634445 15791361 193309093 66202596 72364149 743270896 297240520 264035189 898589962 59916738 307942952 403411309");
            WillReturn.Add("30");
            WillReturn.Add("930579110");
            WillReturn.Add("22697034");
            WillReturn.Add("44652533");
            WillReturn.Add("280533771");
            WillReturn.Add("753567118");
            WillReturn.Add("684927419");
            WillReturn.Add("923477579");
            WillReturn.Add("557613803");
            WillReturn.Add("779616458");
            WillReturn.Add("389130756");
            WillReturn.Add("323671659");
            WillReturn.Add("3117850");
            WillReturn.Add("408004003");
            WillReturn.Add("224808850");
            WillReturn.Add("18421958");
            WillReturn.Add("359047808");
            WillReturn.Add("364572866");
            WillReturn.Add("334631363");
            WillReturn.Add("854759331");
            WillReturn.Add("647435074");
            WillReturn.Add("826055423");
            WillReturn.Add("668443532");
            WillReturn.Add("620408208");
            WillReturn.Add("32237184");
            WillReturn.Add("67299071");
            WillReturn.Add("251185742");
            WillReturn.Add("217292659");
            WillReturn.Add("16181227");
            WillReturn.Add("850865411");
            WillReturn.Add("218577687");
            //4031345
            //3062589
            //2044744
            //2866703
            //4241278
            //3081744
            //3070186
            //3564353
            //6718521
            //8642412
            //2455689
            //2118050
            //700867
            //4223790
            //1212487
            //8277581
            //13802639
            //2447438
            //251455
            //887671
            //1596266
            //9299319
            //10219916
            //1819374
            //607842
            //12849447
            //11739981
            //389866
            //648537
            //10454953
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static long[] mAArr;

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

        long[] BArr = InputList.Skip(3).Select(pX => long.Parse(pX)).ToArray();

        var sb = new System.Text.StringBuilder();
        foreach (long EachB in BArr) {
            sb.Append(ExecSanbuntansaku(EachB));
            sb.AppendLine();
        }
        Console.WriteLine(sb.ToString());
    }

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

        // Indを引数として、関数値を返す
        Func<long, long> CalcFunc = pInd =>
        {
            return Math.Abs(pBVal - mAArr[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();
    }
}

解説

distinctメソッドで重複をなくしてから、三分探索してます。