ABC319-E Bus Stops

問題へのリンク

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("4 2 3");
            WillReturn.Add("5 4");
            WillReturn.Add("6 6");
            WillReturn.Add("3 1");
            WillReturn.Add("7");
            WillReturn.Add("13");
            WillReturn.Add("0");
            WillReturn.Add("710511029");
            WillReturn.Add("136397527");
            WillReturn.Add("763027379");
            WillReturn.Add("644706927");
            WillReturn.Add("447672230");
            //34
            //22
            //710511052
            //136397548
            //763027402
            //644706946
            //447672250
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    struct PTInfoDef
    {
        internal long P;
        internal long T;
    }
    static List<PTInfoDef> mPTInfoList = new List<PTInfoDef>();

    static long mX;
    static long mY;

    static void Main()
    {
        var wkList = new List<long>();
        for (long I = 2; I <= 8; I++) {
            wkList.Add(I);
        }
        long LCM = DeriveLCM(wkList, long.MaxValue);

        List<string> InputList = GetInputList();

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

        SplitAct(InputList[0]);
        long N = wkArr[0];
        mX = wkArr[1];
        mY = wkArr[2];

        foreach (string EachStr in InputList.Skip(1).Take((int)N - 1)) {
            SplitAct(EachStr);
            PTInfoDef WillAdd;
            WillAdd.P = wkArr[0];
            WillAdd.T = wkArr[1];
            mPTInfoList.Add(WillAdd);
        }

        var sb = new System.Text.StringBuilder();
        foreach (string EachStr in InputList.Skip(1 + (int)N)) {
            SplitAct(EachStr);
            long Q = long.Parse(EachStr);

            long Answer = Q + mX + DeriveBusCost((Q + mX) % LCM) + mY;
            sb.Append(Answer);
            sb.AppendLine();
        }
        Console.Write(sb.ToString());
    }

    static Dictionary<long, long> mCostDict = new Dictionary<long, long>();

    // 最初にバス停に到着した時のModを引数として、バス移動のコストを返す
    static long DeriveBusCost(long pStaMod)
    {
        if (mCostDict.ContainsKey(pStaMod)) {
            return mCostDict[pStaMod];
        }
        long CurrTime = pStaMod;
        foreach (PTInfoDef EachPTInfo in mPTInfoList) {
            long P = EachPTInfo.P;
            long T = EachPTInfo.T;
            if (CurrTime % P == 0) {
                CurrTime += T;
                continue;
            }

            long Mod = CurrTime % P;
            long Add = P - Mod;
            CurrTime += Add;
            CurrTime += T;
        }
        return mCostDict[pStaMod] = CurrTime - pStaMod;
    }

    // 列挙を引数として、最小公倍数を返す
    static long DeriveLCM(IEnumerable<long> pEnum, long pLimit)
    {
        long LCM = pEnum.First();
        foreach (long EachLong in pEnum) {
            LCM = DeriveLCM2(LCM, EachLong);
            if (LCM > pLimit) {
                break;
            }
        }
        return LCM;
    }

    // 2つの数のLCMを求める
    static long DeriveLCM2(long p1, long p2)
    {
        long GCD = DeriveGCD(p1, p2);
        return (p1 / GCD) * p2;
    }

    // ユークリッドの互除法で2数の最大公約数を求める
    static long DeriveGCD(long pVal1, long pVal2)
    {
        long WarareruKazu = pVal2;
        long WaruKazu = pVal1;

        while (true) {
            long Amari = WarareruKazu % WaruKazu;
            if (Amari == 0) return WaruKazu;
            WarareruKazu = WaruKazu;
            WaruKazu = Amari;
        }
    }
}

解説

全ての周期のLCMでのModが決まれば、
バス移動の合計コストが決まるので、

DeriveBusCostメソッドの、引数と戻り値のペアをキャッシュしてます。