ABC119-D Lazy Faith

問題へのリンク

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 4");
            WillReturn.Add("100");
            WillReturn.Add("600");
            WillReturn.Add("400");
            WillReturn.Add("900");
            WillReturn.Add("1000");
            WillReturn.Add("150");
            WillReturn.Add("2000");
            WillReturn.Add("899");
            WillReturn.Add("799");
            //350
            //1400
            //301
            //399
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("1 1 3");
            WillReturn.Add("1");
            WillReturn.Add("10000000000");
            WillReturn.Add("2");
            WillReturn.Add("9999999999");
            WillReturn.Add("5000000000");
            //10000000000
            //10000000000
            //14999999998
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

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

        int[] wkArr = InputList[0].Split(' ').Select(pX => int.Parse(pX)).ToArray();
        int A = wkArr[0];
        int B = wkArr[1];
        int Q = wkArr[2];

        long[] SArr = InputList.Skip(1).Take(A).Select(pX => long.Parse(pX)).ToArray();
        Array.Sort(SArr);

        long[] TArr = InputList.Skip(1 + A).Take(B).Select(pX => long.Parse(pX)).ToArray();
        Array.Sort(TArr);

        long[] QArr = InputList.Skip(1 + A + B).Select(pX => long.Parse(pX)).ToArray();

        foreach (long EachLong in QArr) {
            var AnswerKouhoList = new List<long>();

            AnswerKouhoList.Add(Solve(EachLong, false, SArr, false, TArr));
            AnswerKouhoList.Add(Solve(EachLong, false, SArr, true, TArr));
            AnswerKouhoList.Add(Solve(EachLong, true, SArr, false, TArr));
            AnswerKouhoList.Add(Solve(EachLong, true, SArr, true, TArr));

            AnswerKouhoList.Add(Solve(EachLong, false, TArr, false, SArr));
            AnswerKouhoList.Add(Solve(EachLong, false, TArr, true, SArr));
            AnswerKouhoList.Add(Solve(EachLong, true, TArr, false, SArr));
            AnswerKouhoList.Add(Solve(EachLong, true, TArr, true, SArr));

            AnswerKouhoList.RemoveAll(pX => pX == -1);
            Console.WriteLine(AnswerKouhoList.Min());
        }
    }

    // 二分法を2回実行する
    static long Solve(long pCurrPos, bool pIsLeft1, long[] pTargetArr1, bool pIsLeft2, long[] pTargetArr2)
    {
        long SecondPos;
        if (pIsLeft1) {
            SecondPos = ExecNibunhouLeft(pCurrPos, pTargetArr1);
        }
        else {
            SecondPos = ExecNibunhouRight(pCurrPos, pTargetArr1);
        }
        if (SecondPos == -1) return -1;

        long ThirdPos;
        if (pIsLeft2) {
            ThirdPos = ExecNibunhouLeft(SecondPos, pTargetArr2);
        }
        else {
            ThirdPos = ExecNibunhouRight(SecondPos, pTargetArr2);
        }
        if (ThirdPos == -1) return -1;

        long Result = Math.Abs(pCurrPos - SecondPos) + Math.Abs(SecondPos - ThirdPos);
        return Result;
    }

    // 二分法で、指定した値以上の最小値を返す
    static long ExecNibunhouRight(long pBase, long[] pArr)
    {
        int L = 0;
        int R = pArr.GetUpperBound(0);

        // 特殊ケース1
        if (pArr[0] >= pBase) {
            return pArr[0];
        }

        // 特殊ケース2
        if (pArr[R] < pBase) {
            return -1;
        }

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

            if (pArr[Mid] < pBase) {
                L = Mid;
            }
            else {
                R = Mid;
            }
        }
        return pArr[R];
    }

    // 二分法で、指定した値以下の最大値を返す
    static long ExecNibunhouLeft(long pBase, long[] pArr)
    {
        int L = 0;
        int R = pArr.GetUpperBound(0);

        // 特殊ケース1
        if (pArr[0] > pBase) {
            return -1;
        }

        // 特殊ケース2
        if (pArr[R] <= pBase) {
            return pArr[R];
        }

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

            if (pArr[Mid] <= pBase) {
                L = Mid;
            }
            else {
                R = Mid;
            }
        }
        return pArr[L];
    }
}

解説

1回目の移動は、
左の寺に移動
左の神社に移動
右の寺に移動
右の神社に移動
の4通りあり、

その後の移動は、
左右どちらかの寺か神社に移動なので
この 4*2=8 通りの移動距離を、二分法で求めてます。