ABC024-C 民族大移動

問題へのリンク

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("10 10 3");
            WillReturn.Add("1 5");
            WillReturn.Add("3 6");
            WillReturn.Add("7 10");
            WillReturn.Add("5 8");
            WillReturn.Add("4 4");
            WillReturn.Add("1 4");
            WillReturn.Add("2 9");
            WillReturn.Add("1 3");
            WillReturn.Add("1 1");
            WillReturn.Add("4 5");
            WillReturn.Add("1 6");
            WillReturn.Add("2 7");
            WillReturn.Add("10 1");
            //2
            //4
            //8
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("10 10 4");
            WillReturn.Add("1 2");
            WillReturn.Add("2 4");
            WillReturn.Add("3 6");
            WillReturn.Add("4 8");
            WillReturn.Add("5 10");
            WillReturn.Add("9 10");
            WillReturn.Add("7 8");
            WillReturn.Add("5 6");
            WillReturn.Add("3 5");
            WillReturn.Add("1 3");
            WillReturn.Add("10 1");
            WillReturn.Add("3 8");
            WillReturn.Add("2 4");
            WillReturn.Add("1 3");
            //10
            //4
            //2
            //2
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("314159265 10 1");
            WillReturn.Add("1 10000");
            WillReturn.Add("500 12031");
            WillReturn.Add("1414 113232");
            WillReturn.Add("111111 777777");
            WillReturn.Add("666661 23423423");
            WillReturn.Add("12345678 123456789");
            WillReturn.Add("111111111 314159265");
            WillReturn.Add("112334 235235235");
            WillReturn.Add("1 223445");
            WillReturn.Add("314 1592");
            WillReturn.Add("1 314159265");
            //7
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    struct LRInfoDef
    {
        internal int L;
        internal int R;
    }

    class MinzokuInfoDef
    {
        internal int CurrPos;
        internal int GoalPos;
        internal int GoalDay;
    }

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

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

        SplitAct(InputList[0]);
        int D = wkArr[1];

        var LRInfoList = new List<LRInfoDef>();
        foreach (string EachStr in InputList.Skip(1).Take(D)) {
            SplitAct(EachStr);
            LRInfoDef WillAdd;
            WillAdd.L = wkArr[0];
            WillAdd.R = wkArr[1];
            LRInfoList.Add(WillAdd);
        }

        var MinzokuInfoList = new List<MinzokuInfoDef>();
        foreach (string EachStr in InputList.Skip(1 + D)) {
            SplitAct(EachStr);
            MinzokuInfoDef WillAdd = new MinzokuInfoDef();
            WillAdd.CurrPos = wkArr[0];
            WillAdd.GoalPos = wkArr[1];
            WillAdd.GoalDay = int.MaxValue;
            MinzokuInfoList.Add(WillAdd);
        }

        for (int I = 0; I <= LRInfoList.Count - 1; I++) {
            foreach (MinzokuInfoDef EachMinzokuInfo in MinzokuInfoList) {
                if (EachMinzokuInfo.CurrPos == EachMinzokuInfo.GoalPos) {
                    continue;
                }
                if (LRInfoList[I].L <= EachMinzokuInfo.CurrPos &&
                    EachMinzokuInfo.CurrPos <= LRInfoList[I].R) {

                    // 現在位置とゴールとの大小関係で場合分け
                    if (EachMinzokuInfo.CurrPos < EachMinzokuInfo.GoalPos) {
                        EachMinzokuInfo.CurrPos = Math.Min(EachMinzokuInfo.GoalPos, LRInfoList[I].R);
                    }
                    else {
                        EachMinzokuInfo.CurrPos = Math.Max(EachMinzokuInfo.GoalPos, LRInfoList[I].L);
                    }
                }
                if (EachMinzokuInfo.CurrPos == EachMinzokuInfo.GoalPos) {
                    EachMinzokuInfo.GoalDay = I + 1;
                }
            }
        }
        MinzokuInfoList.ForEach(pX => Console.WriteLine(pX.GoalDay));
    }
}

解説

貪欲法で、移動可能な範囲ごとに、
可能な限りゴールに近づく移動を行ってます。