ABC063-D Widespread

■■■問題■■■

あなたが散歩していると、突然N体の魔物が出現しました。
それぞれの魔物は体力という値を持ち、i体目の魔物の出現時の体力はhiです。
体力が0以下となった魔物は直ちに消滅します。

幸い、あなたは熟練の魔法使いであり、爆発を引き起こして魔物を攻撃できます。
一回の爆発では、以下のように魔物の体力を減らすことができます。

●生存している魔物を一体選び、その魔物を中心に爆発を引き起こす。
  爆発の中心となる魔物の体力はA減り、
  その他の魔物の体力はそれぞれB減る。
  ここで、AとBはあらかじめ定まった値であり、A > B である。

すべての魔物を消し去るためには、
最小で何回の爆発を引き起こす必要があるでしょうか？

■■■入力■■■

N A B
h1
h2
・
・
・
hN

●入力値はすべて整数である
●1 <= N <= 10万
●1 <= B < A <= 10億
●1 <= hi <= 10億

■■■出力■■■

すべての魔物を消し去るために必要な最小の爆発の回数を出力せよ

C#のソース

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static string InputPattern = "Input1";

    static List<string> GetInputList()
    {
        var WillReturn = new List<string>();

        if (InputPattern == "Input1") {
            WillReturn.Add("4 5 3");
            WillReturn.Add("8");
            WillReturn.Add("7");
            WillReturn.Add("4");
            WillReturn.Add("2");
            //2
            //以下のようにして、2回の爆発ですべての魔物を消し去ることができます。
            //●まず、体力が8の魔物を中心に爆発を引き起こす。
            //  4体の魔物の体力はそれぞれ 3,4,1,-1となり、最後の魔物は消滅する。
            //●次に、残りの体力が4の魔物を中心に爆発を引き起こす。
            //  残っていた3体の魔物の体力はそれぞれ 0,-1,-2となり、すべての魔物が消滅する。
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("2 10 4");
            WillReturn.Add("20");
            WillReturn.Add("20");
            //4
            //それぞれの魔物を中心に2回ずつ、
            //合計で4回の爆発を引き起こす必要があります。
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("5 2 1");
            WillReturn.Add("900000000");
            WillReturn.Add("900000000");
            WillReturn.Add("1000000000");
            WillReturn.Add("1000000000");
            WillReturn.Add("1000000000");
            //800000000
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static long mA;
    static long mB;
    static long[] mHArr;

    static void Main()
    {
        List<string> InputList = GetInputList();
        long[] wkArr = InputList[0].Split(' ').Select(X => long.Parse(X)).ToArray();

        mA = wkArr[1];
        mB = wkArr[2];

        mHArr = InputList.Skip(1).Select(X => long.Parse(X)).ToArray();
        // 降順にソートしておく
        Array.Sort(mHArr, (A, B) => B.CompareTo(A));

        Console.WriteLine(ExecNibunHou());
    }

    // 2分法で何回の爆発が必要かを調べる
    static long ExecNibunHou()
    {
        long L = 0;
        long R = mHArr.Sum(X => X / mA + 1);

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

            bool IsOK = DeriveIsOK(Mid);
            if (IsOK) R = Mid;
            else L = Mid;
        }
        return R;
    }

    // K回の爆発でOKかを返す
    static bool DeriveIsOK(long pK)
    {
        // 爆発回数
        long BakuhatuCnt = 0;

        // 余波の合計
        long YohaSum = pK * mB;

        foreach (long EachH in mHArr) {
            long RestH = EachH - YohaSum;
            if (RestH <= 0) break;

            long wkDiff = mA - mB;
            long CurrBakuhatuCnt = RestH / wkDiff;
            if (EachH % wkDiff > 0) CurrBakuhatuCnt++;

            BakuhatuCnt += CurrBakuhatuCnt;
            if (BakuhatuCnt > pK) return false;
        }
        return true;
    }
}

解説

K回の爆発でOKかを判定するメソッドを用意し、2分法を使ってます。

類題

ARC050-B 花束