ABC193-E Oversleeping

問題へのリンク

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");
            WillReturn.Add("5 2 7 6");
            WillReturn.Add("1 1 3 1");
            WillReturn.Add("999999999 1 1000000000 1");
            //20
            //infinity
            //1000000000999999999
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    struct RangeInfoDef
    {
        internal long RangeSta;
        internal long RangeEnd;
    }

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

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

        var sb = new System.Text.StringBuilder();
        foreach (string EachStr in InputList.Skip(1)) {
            SplitAct(EachStr);
            long X = wkArr[0];
            long Y = wkArr[1];
            long P = wkArr[2];
            long Q = wkArr[3];

            var TrainRangeList = new List<RangeInfoDef>();
            var TakahashiRangeList = new List<RangeInfoDef>();

            // 電車の区間情報(4要素)を求める
            for (int I = 0; I <= 3; I++) {
                RangeInfoDef WillAdd;
                if (I == 0) {
                    WillAdd.RangeSta = 0;
                    WillAdd.RangeEnd = X - 1;
                }
                else {
                    RangeInfoDef LastRange = TrainRangeList.Last();
                    WillAdd.RangeSta = LastRange.RangeEnd + 1;
                    WillAdd.RangeEnd = WillAdd.RangeSta;
                    if (I == 1 || I == 3) {
                        WillAdd.RangeEnd += Y - 1;
                    }
                    if (I == 2) {
                        WillAdd.RangeEnd += X - 1;
                    }
                }
                TrainRangeList.Add(WillAdd);
            }

            // 高橋君の区間情報(2要素)を求める
            for (int I = 0; I <= 1; I++) {
                RangeInfoDef WillAdd;
                if (I == 0) {
                    WillAdd.RangeSta = 0;
                    WillAdd.RangeEnd = P - 1;
                }
                else {
                    WillAdd.RangeSta = TakahashiRangeList[0].RangeEnd + 1;
                    WillAdd.RangeEnd = WillAdd.RangeSta + Q - 1;
                }
                TakahashiRangeList.Add(WillAdd);
            }

            // 電車の周期を求める
            long Syuuki1 = (X + Y) * 2;

            // 高橋君の周期を求める
            long Syuuki2 = (P + Q);

            var AnswerKouho = new List<long>();
            for (long I = TrainRangeList[1].RangeSta; I <= TrainRangeList[1].RangeEnd; I++) {
                for (long J = TakahashiRangeList[1].RangeSta; J <= TakahashiRangeList[1].RangeEnd; J++) {
                    var Result = CRT.ChineseRem(I, Syuuki1, J, Syuuki2);
                    if (Result.m == -1) continue;
                    AnswerKouho.Add(Result.r);
                }
            }

            if (AnswerKouho.Count > 0) {
                Console.WriteLine(AnswerKouho.Min());
            }
            else {
                Console.WriteLine("infinity");
            }
        }
    }
}

// 中国剰余定理クラス
internal class CRT
{
    // 負の数にも対応した mod
    // 例えば -17 を 5 で割った余りは本当は 3 (-17 ≡ 3 (mod. 5))
    // しかし単に -17 % 5 では -2 になってしまう
    static long mod(long a, long m)
    {
        return (a % m + m) % m;
    }

    // 拡張 Euclid の互除法
    // ap + bq = gcd(a, b) となる (p, q) を求め、d = gcd(a, b) をリターンします
    static long extGcd(long a, long b, ref long p, ref long q)
    {
        if (b == 0) { p = 1; q = 0; return a; }
        long d = extGcd(b, a % b, ref q, ref p);
        q -= a / b * p;
        return d;
    }

    internal struct CRT_Result_Def
    {
        internal long r;
        internal long m;
    }

    // 中国剰余定理 (2元の場合)
    // リターン値を (r, m) とすると解は x ≡ r (mod. m)
    // 解なしの場合は (0, -1) をリターン
    internal static CRT_Result_Def ChineseRem(long Div1, long Mod1, long Div2, long Mod2)
    {
        long p = 1, q = 0;
        long d = extGcd(Mod1, Mod2, ref p, ref q); // p is inv of m1/d (mod. m2/d)
        if ((Div2 - Div1) % d != 0) return new CRT_Result_Def() { r = 0, m = -1 };
        long m = Mod1 * (Mod2 / d); // lcm of (m1, m2)
        long tmp = (Div2 - Div1) / d * p % (Mod2 / d);
        long r = mod(Div1 + Mod1 * tmp, m);
        return new CRT_Result_Def() { r = r, m = m };
    }

    // 中国剰余定理 (n元の場合)
    // リターン値を (r, m) とすると解は x ≡ r (mod. m)
    // 解なしの場合は (0, -1) をリターン
    internal static CRT_Result_Def ChineseRem(List<long> pModList, List<long> pDivList)
    {
        long r = 0, M = 1;
        for (int i = 0; i < pModList.Count; i++) {
            long p = 1, q = 0;
            long d = extGcd(M, pDivList[i], ref p, ref q); // p is inv of M/d (mod. m[i]/d)
            if ((pModList[i] - r) % d != 0) {
                return new CRT_Result_Def() { r = 0, m = -1 };
            }
            long tmp = (pModList[i] - r) / d * p % (pDivList[i] / d);
            r += M * tmp;
            M *= pDivList[i] / d;
        }
        return new CRT_Result_Def() { r = mod(r, M), m = M };
    }
}

解説

考察すると、
電車の移動と
高橋君の寝る起きる
は、周期性があると分かります。

後は、閉区間の連続で区間を管理しつつ、
中国剰余定理の問題に帰着させてます。