AOJ 0622 JOI国のお散歩事情 (Walking in JOI Kingdom)

問題へのリンク

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 5 3");
            WillReturn.Add("-8 1");
            WillReturn.Add("-4 2");
            WillReturn.Add("-2 2");
            WillReturn.Add("4 2");
            WillReturn.Add("10 1");
            WillReturn.Add("1");
            WillReturn.Add("3");
            WillReturn.Add("5");
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("7 18 5");
            WillReturn.Add("-100 1");
            WillReturn.Add("-56 2");
            WillReturn.Add("-34 1");
            WillReturn.Add("-30 1");
            WillReturn.Add("-22 1");
            WillReturn.Add("-4 2");
            WillReturn.Add("18 2");
            WillReturn.Add("1");
            WillReturn.Add("3");
            WillReturn.Add("4");
            WillReturn.Add("5");
            WillReturn.Add("7");
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    struct HouseInfoDef
    {
        internal long Pos;
        internal long Vect;
    }
    static List<HouseInfoDef> mHouseInfoList = new List<HouseInfoDef>();

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

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

        SplitAct(InputList[0]);
        long N = wkArr[0];
        long T = wkArr[1];

        foreach (string EachStr in InputList.Skip(1).Take((int)N)) {
            SplitAct(EachStr);
            long Pos = wkArr[0];
            long Vect = wkArr[1];
            HouseInfoDef WillAdd;
            WillAdd.Pos = Pos;
            WillAdd.Vect = Vect;
            mHouseInfoList.Add(WillAdd);
        }

        var StopPosSet = new HashSet<long>();
        int UB = mHouseInfoList.Count - 1;
        for (int I = 0; I <= UB; I++) {
            if (mHouseInfoList[I].Vect == 1) {
                if (I + 1 <= UB && mHouseInfoList[I + 1].Vect == 2) {
                    long StopPos = (mHouseInfoList[I + 1].Pos + mHouseInfoList[I].Pos) / 2;
                    StopPosSet.Add(StopPos);
                }
            }
        }

        List<long> StopPosList = StopPosSet.ToList();
        StopPosList.Sort();

        foreach (string EachStr in InputList.Skip(1 + (int)N)) {
            int Q = int.Parse(EachStr);
            HouseInfoDef CurrHouseInfo = mHouseInfoList[Q - 1];

            long CurrPos = CurrHouseInfo.Pos;

            if (CurrHouseInfo.Vect == 1) {
                int ResultInd = ExecNibunhou_LowerBound(CurrPos, StopPosList);
                if (ResultInd == -1 || StopPosList[ResultInd] < CurrPos) {
                    Console.WriteLine(CurrPos + T);
                }
                else if (Math.Abs(StopPosList[ResultInd] - CurrPos) >= T) {
                    Console.WriteLine(CurrPos + T);
                }
                else {
                    Console.WriteLine(StopPosList[ResultInd]);
                }
            }
            else {
                int ResultInd = ExecNibunhou_LowerOrEqual_Max(CurrPos, StopPosList);
                if (ResultInd == -1 || CurrPos < StopPosList[ResultInd]) {
                    Console.WriteLine(CurrPos - T);
                }
                else if (Math.Abs(StopPosList[ResultInd] - CurrPos) >= T) {
                    Console.WriteLine(CurrPos - T);
                }
                else {
                    Console.WriteLine(StopPosList[ResultInd]);
                }
            }
        }
    }

    // 二分法で、Val以上で最小の値を持つ、添字を返す
    static int ExecNibunhou_LowerBound(long pVal, List<long> pList)
    {
        if (pList.Count == 0) return -1;

        // 最後の要素がVal未満の特殊ケース
        if (pVal > pList.Last()) {
            return -1;
        }
        // 最初の要素がVal以上の特殊ケース
        if (pVal <= pList[0]) {
            return 0;
        }

        int L = 0;
        int R = pList.Count - 1;

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

            if (pList[Mid] >= pVal) {
                R = Mid;
            }
            else {
                L = Mid;
            }
        }
        return R;
    }

    // 二分法で、Val以下で最大の値を持つ、添字を返す
    static int ExecNibunhou_LowerOrEqual_Max(long pVal, List<long> pList)
    {
        if (pList.Count == 0) return -1;

        // 最後の要素がVal以下の特殊ケース
        if (pVal >= pList.Last()) {
            return pList.Count - 1;
        }
        // 最初の要素がVal超えの特殊ケース
        if (pVal < pList[0]) {
            return -1;
        }

        int L = 0;
        int R = pList.Count - 1;

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

            if (pList[Mid] <= pVal) {
                L = Mid;
            }
            else {
                R = Mid;
            }
        }
        return L;
    }
}

解説

考察すると、
右向きと左向きが隣接した場合に、
移動がStopされる座標が発生すると分かります。

後は、二分探索で解けます。