ARC118-B Village of M People

問題へのリンク

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 7 20");
            WillReturn.Add("1 2 4");
            //3 6 11
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("3 3 100");
            WillReturn.Add("1 1 1");
            //34 33 33
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("6 10006 10");
            WillReturn.Add("10000 3 2 1 0 0");
            //10 0 0 0 0 0
        }
        else if (InputPattern == "Input4") {
            WillReturn.Add("7 78314 1000");
            WillReturn.Add("53515 10620 7271 3817 1910 956 225");
            //683 136 93 49 24 12 3
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static long mN;
    static long mM;

    static long[] mAArr;
    static long UB;

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

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

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

        List<long> KagenList;
        List<long> JyougenList;

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

            if (CanAchieve(Mid, out KagenList, out JyougenList)) {
                R = Mid;
            }
            else {
                L = Mid;
            }
        }
        CanAchieve(R, out KagenList, out JyougenList);

        long KagenSum = KagenList.Sum();
        long Rest = 0;
        if (KagenSum < mM) {
            Rest = mM - KagenSum;
        }

        var AnswerList = new List<long>();
        for (int I = 0; I <= UB; I++) {
            if (Rest > 0) {
                long Diff = JyougenList[I] - KagenList[I];
                long AddVal = Math.Min(Diff, Rest);
                Rest -= AddVal;
                AnswerList.Add(KagenList[I] + AddVal);
            }
            else {
                AnswerList.Add(KagenList[I]);
            }
        }

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

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

    // 全てK以下にできるかを返す
    static bool CanAchieve(long pK, out List<long> pKagenList, out List<long> pJyougenList)
    {
        pKagenList = new List<long>();
        pJyougenList = new List<long>();

        long KagenSum = 0;
        long JyougenSum = 0;
        for (int I = 0; I <= UB; I++) {
            long CurrKagen;
            long CurrJyougen;

            SolveHutousiki(pK, mAArr[I], out CurrKagen, out CurrJyougen);
            KagenSum += CurrKagen;
            JyougenSum += CurrJyougen;

            pKagenList.Add(CurrKagen);
            pJyougenList.Add(CurrJyougen);
        }

        if (KagenSum <= mM && mM <= JyougenSum) {
            return true;
        }
        return false;
    }

    // 連立不等式 -K <= NB - AM <= K
    // をBについて解き(Nの符号は正)
    // Bの下限と上限を返す
    static void SolveHutousiki(long pK, long pA, out long pKagen, out long pJyougen)
    {
        pKagen = -1;
        pJyougen = -1;

        long Sahen = (-pK + pA * mM);
        pKagen = Sahen / mN;
        if (Sahen % mN > 0) {
            if (Sahen > 0) pKagen++;
        }

        long Uhen = pK + pA * mM;
        pJyougen = Uhen / mN;
        if (Uhen % mN > 0) {
            if (Uhen < 0) pJyougen--;
        }
    }
}

解説

max(A,B,C) <= 10 は
Aが10以下 かつ
Bが10以下 かつ
Cが10以下 と同値となります。

なので
abs(Bi/M - Ai/N) に MN(MNは必ず正なので不等式の向きは変わらない)を掛けた値を、
全てK以下にできるかという判定関数を作り
二分探索で解くことができます。