AOJ 0694 安全点検

問題へのリンク(AOJ)
問題へのリンク(AtCoder)

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 3 4");
            WillReturn.Add("4 2 4");
            //7
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("6 1");
            WillReturn.Add("1 4 5 6 11 15");
            WillReturn.Add("12 5 9 8 10 4");
            //63
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("6 2");
            WillReturn.Add("1 4 5 6 11 15");
            WillReturn.Add("12 5 9 8 10 4");
            //35
        }
        else if (InputPattern == "Input4") {
            WillReturn.Add("6 5");
            WillReturn.Add("1 4 5 6 11 15");
            WillReturn.Add("12 5 9 8 10 4");
            //19
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static long[] GetSplitArr(string pStr)
    {
        return (pStr == "" ? new string[0] : pStr.Split(' ')).Select(pX => long.Parse(pX)).ToArray();
    }

    struct ABInfoDef
    {
        internal long A;
        internal long B;
    }
    static List<ABInfoDef> mABInfoList = new List<ABInfoDef>();
    static long mMaxA = long.MinValue;

    static long mK;

    static void Main()
    {
        List<string> InputList = GetInputList();
        long[] wkArr = GetSplitArr(InputList[0]);
        mK = wkArr[1];

        long[] AArr = GetSplitArr(InputList[1]);
        long[] BArr = GetSplitArr(InputList[2]);

        for (long I = 0; I <= AArr.GetUpperBound(0); I++) {
            ABInfoDef WillAdd;
            WillAdd.A = AArr[I];
            WillAdd.B = BArr[I];
            mABInfoList.Add(WillAdd);

            mMaxA = Math.Max(mMaxA, AArr[I]);
        }
        // Aの昇順にソート
        mABInfoList = mABInfoList.OrderBy(pX => pX.A).ToList();

        long L = 0;
        long R = long.MaxValue;

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

            bool Result = CanAchieve(Mid);
            if (Result) {
                R = Mid;
            }
            else {
                L = Mid;
            }

        }
        Console.WriteLine(R);
    }

    // X分で全て点検可能かを返す
    static bool CanAchieve(long pX)
    {
        // 移動だけで時間切れなら不可
        if (mMaxA >= pX) return false;

        int Ind_N = 0;
        int UB_N = mABInfoList.Count - 1;
        long RestB = mABInfoList[0].B;

        long RestK = mK;
        long LastManTime = 0;
        long LastManPos = 0;

        while (true) {
            if (RestB == 0) {
                Ind_N++;
                if (Ind_N > UB_N) return true;
                RestB = mABInfoList[Ind_N].B;
                continue;
            }

            if (LastManTime > 0) {
                if (LastManPos < mABInfoList[Ind_N].A) {
                    long MoveTime = mABInfoList[Ind_N].A - LastManPos;
                    LastManTime -= MoveTime;
                    LastManPos = mABInfoList[Ind_N].A;
                    continue;
                }
                long MinVal = Math.Min(LastManTime, RestB);
                LastManTime -= MinVal;
                RestB -= MinVal;
                continue;
            }

            // 何人必要かを調べる
            long RestTime = pX - mABInfoList[Ind_N].A;
            long NeedK = RestB / RestTime;
            if (RestB % RestTime > 0) {
                NeedK++;
            }
            RestK -= NeedK;
            if (RestK < 0) return false;

            LastManTime = RestTime - RestB % RestTime;
            LastManPos = mABInfoList[Ind_N].A;
            RestB = 0;
        }
    }
}

解説

「CODE FESTIVAL 2015予選A D 壊れた電車」の類題だと思います。

X分で全て点検可能かの判定メソッドを作成すれば、二分探索で解けます。

Nの上限が10の5乗で
Kの上限が10の9乗なので
判定メソッドでは、Nのループで判定しないとTLEになります。

判定メソッドでは、
点検必要箇所をAの昇順に見ていき
何人の大工がいれば点検できるかと、最後の大工の時間の余りを調べ、
左から貪欲に、大工と点検箇所をマッチングさせてます。