ABC415-D Get Many Stickers

問題へのリンク

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("5 3");
            WillReturn.Add("5 1");
            WillReturn.Add("4 3");
            WillReturn.Add("3 1");
            //3
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("3 3");
            WillReturn.Add("5 1");
            WillReturn.Add("5 1");
            WillReturn.Add("4 2");
            //0
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("415 8");
            WillReturn.Add("327 299");
            WillReturn.Add("413 396");
            WillReturn.Add("99 67");
            WillReturn.Add("108 51");
            WillReturn.Add("195 98");
            WillReturn.Add("262 180");
            WillReturn.Add("250 175");
            WillReturn.Add("234 187");
            //11
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    struct ChangeInfo
    {
        internal long MinusCnt;
        internal long PlusCnt;
    }
    static List<ChangeInfo> mChangeInfoList = new List<ChangeInfo>();

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

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

        SplitAct(InputList[0]);
        long CurrCnt = wkArr[0];

        foreach (string EachStr in InputList.Skip(1)) {
            SplitAct(EachStr);
            ChangeInfo WillAdd;
            WillAdd.MinusCnt = wkArr[0];
            WillAdd.PlusCnt = wkArr[1];
            mChangeInfoList.Add(WillAdd);
        }
        mChangeInfoList = mChangeInfoList.OrderByDescending(pX => -pX.MinusCnt + pX.PlusCnt).ToList();

        var Que = new Queue<ChangeInfo>(mChangeInfoList);

        long Answer = 0;
        while (true) {
            if (Que.Count == 0) break;
            ChangeInfo Peeked = Que.Peek();
            if (Peeked.MinusCnt > CurrCnt) {
                Que.Dequeue();
                continue;
            }

            long Kaisuu = DeriveKaisuu(CurrCnt, -Peeked.MinusCnt + Peeked.PlusCnt, Peeked.MinusCnt);
            CurrCnt -= Peeked.MinusCnt * Kaisuu;
            CurrCnt += Peeked.PlusCnt * Kaisuu;
            Answer += Kaisuu;

            // シュミレーション(回数は2べき)
            for (long I = 1; I < long.MaxValue; I *= 2) {
                if (CurrCnt - Peeked.MinusCnt * I >= 0) {
                    CurrCnt -= Peeked.MinusCnt * I;
                    CurrCnt += Peeked.PlusCnt * I;
                    Answer += I;
                }
                else {
                    break;
                }
            }
            continue;
        }
        Console.WriteLine(Answer);
    }

    // 一次不等式 A-Bx >= pC を解く
    // xの符号が負なので、解の符号は反転する
    static long DeriveKaisuu(long pA, long pB, long pC)
    {
        long Uhen = pC - pA;
        return Uhen / pB;
    }
}

解説

受験算数でよくある、ただジュース問題に近いです。

(-渡す数 + もらう数)の降順で好条件なのでキューに入れる。
交換できるだけ交換。
最大交換回数は、一次不等式を解くメソッドで求め。
残りは2べきの試行回数でシュミる。

という方針で解いてます。