ABC023-D 射撃王

問題へのリンク

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("5 6");
            WillReturn.Add("12 4");
            WillReturn.Add("14 7");
            WillReturn.Add("21 2");
            //23
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("6");
            WillReturn.Add("100 1");
            WillReturn.Add("100 1");
            WillReturn.Add("100 1");
            WillReturn.Add("100 1");
            WillReturn.Add("100 1");
            WillReturn.Add("1 30");
            //105
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    struct HSInfoDef
    {
        internal long H;
        internal long S;
    }

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

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

        var HSInfoList = new List<HSInfoDef>();
        foreach (string EachStr in InputList.Skip(1)) {
            SplitAct(EachStr);
            HSInfoDef WillAdd;
            WillAdd.H = wkArr[0];
            WillAdd.S = wkArr[1];
            HSInfoList.Add(WillAdd);
        }
        long Result1 = Solve(HSInfoList);
        Console.WriteLine(Result1);
    }

    static long Solve(List<HSInfoDef> pHSInfoList)
    {
        if (pHSInfoList.Count == 1) {
            return pHSInfoList[0].H;
        }

        //二分法で解く
        long L = 0;
        long R = long.MaxValue;

        while (L + 1 < R) {
            long Mid = long.MaxValue / 2;
            if (R < long.MaxValue) {
                Mid = (L + R) / 2;
            }

            if (CanAchive(Mid, pHSInfoList)) {
                R = Mid;
            }
            else {
                L = Mid;
            }
        }
        return R;
    }

    // 全ての風船を、高さH以下で割れるかを返す
    static bool CanAchive(long pLimitHeight, List<HSInfoDef> pHSInfoList)
    {
        if (pHSInfoList.Exists(pX => pX.H > pLimitHeight)) {
            return false;
        }

        Dictionary<long, long> ToutatuSecDict = DeriveToutatuSecDict(pLimitHeight, pHSInfoList);
        long[] SecArr = ToutatuSecDict.Values.ToArray();
        Array.Sort(SecArr);

        // 貪欲法でチェックする。
        // 先頭の要素は、最初に割るので、Skipする。
        for (int I = 1; I <= SecArr.GetUpperBound(0); I++) {
            if (SecArr[I] <= I) return false;
        }
        return true;
    }

    // 高さHを超える秒[風船]のDictを返す
    static Dictionary<long, long> DeriveToutatuSecDict(long pTargetHeight, List<HSInfoDef> pHSInfoList)
    {
        var ToutatuSecDict = new Dictionary<long, long>();

        for (int I = 0; I <= pHSInfoList.Count - 1; I++) {
            long Diff = pTargetHeight - pHSInfoList[I].H;

            if (Diff <= 0) {
                ToutatuSecDict[I] = 0;
                continue;
            }
            long Syou = Diff / pHSInfoList[I].S;
            Syou++; // 超える秒なので、商をインクリメント

            ToutatuSecDict[I] = Syou;
        }
        return ToutatuSecDict;
    }
}

解説

達成可能かの判定メソッドを用意して、
答えを二分探索してます。