ABC270-E Apple Baskets on Circle

問題へのリンク

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 0");
            //0 1 0 
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("2 1000000000000");
            WillReturn.Add("1000000000000 1000000000000");
            //500000000000 500000000000 
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static long mK;

    static long[] mAArr;
    static long UB;

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

        mAArr = InputList[1].Split(' ').Select(pX => long.Parse(pX)).ToArray();
        UB = mAArr.GetUpperBound(0);

        // 和がX以下になる中で最大の周回数を求める
        long L = 0;
        long R = mK;

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

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

        // L周した時の状態にする
        long Rest = mK;
        for (long I = 0; I <= UB; I++) {
            long TakeCnt = Math.Min(L, mAArr[I]);
            mAArr[I] -= TakeCnt;
            Rest -= TakeCnt;
        }

        // 1周をシュミレーションする
        for (long I = 0; I <= UB; I++) {
            if (Rest == 0) break;
            if (mAArr[I] == 0) continue;
            mAArr[I]--;
            Rest--;
        }

        Console.WriteLine(LongEnumJoin(" ", mAArr));
    }

    // pX周したときの和が、mK以下かを返す
    static bool CanAchieve(long pX)
    {
        long SumVal = 0;
        for (long I = 0; I <= UB; I++) {
            SumVal += Math.Min(pX, mAArr[I]);
            if (SumVal > mK) return false;
        }
        if (SumVal > mK) return false;
        return true;
    }

    // セパレータとLong型の列挙を引数として、結合したstringを返す
    static string LongEnumJoin(string pSeparater, IEnumerable<long> pEnum)
    {
        string[] StrArr = Array.ConvertAll(pEnum.ToArray(), pX => pX.ToString());
        return string.Join(pSeparater, StrArr);
    }
}

解説

1周の要素数は10の5乗なので
1周ならシュミレーションしても良いです。

なので、合計がK以下で最大何週できるかを
二分探索で求めてから、
最後の1周をシュミレーションしてます。