ABC230-D Destroyer Takahashi

問題へのリンク

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("3 3");
            WillReturn.Add("1 2");
            WillReturn.Add("4 7");
            WillReturn.Add("5 9");
            //2
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("3 3");
            WillReturn.Add("1 2");
            WillReturn.Add("4 7");
            WillReturn.Add("4 9");
            //1
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("5 2");
            WillReturn.Add("1 100");
            WillReturn.Add("1 1000000000");
            WillReturn.Add("101 1000");
            WillReturn.Add("9982 44353");
            WillReturn.Add("1000000000 1000000000");
            //3
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

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

    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 D = wkArr[1];

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

        // 破壊した区間のList
        var DestroyRangeList = new List<LRInfoDef>();

        foreach (LRInfoDef EachLRInfo in LRInfoList) {
            bool WillContinue = false;
            for (int I = DestroyRangeList.Count - 1; 0 <= I; I--) {
                // OverLapの判定
                if (DestroyRangeList[I].L <= EachLRInfo.R && EachLRInfo.L <= DestroyRangeList[I].R) {
                    WillContinue = true;
                    break;
                }
                // 枝切り
                if (DestroyRangeList[I].R < EachLRInfo.L) break;
            }
            if (WillContinue) continue;

            LRInfoDef WillAdd;
            WillAdd.L = EachLRInfo.R;
            WillAdd.R = EachLRInfo.R + D - 1;
            DestroyRangeList.Add(WillAdd);
        }
        Console.WriteLine(DestroyRangeList.Count);
    }
}

解説

区間スケジューリング問題に帰着させてます。

区間の右端の昇順に見ていく。
既に破壊した区間とOverLapしてたら、Continueする。
既に破壊した区間とOverLapしてなければ、区間の右端から破壊する。
というアルゴリズムで解いてます。

類題

ABC103-D Islands War