ABC334-B Christmas Trees

問題へのリンク

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 -1 6");
            //3
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("-2 2 1 1");
            //0
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("-177018739841739480 2436426 -80154573737296504 585335723211047198");
            //273142010859
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static decimal mA;
    static decimal mM;
    static decimal mL;
    static decimal mR;

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

        // Aが原点になるように平行移動
        mL -= mA;
        mR -= mA;

        var ValList = new List<decimal>();
        ValList.AddRange(DeriveValList(mL));
        ValList.AddRange(DeriveValList(mR));

        foreach (decimal EachVal in ValList.OrderBy(pX => pX)) {
            if (EachVal >= mL) {
                mL = EachVal;
                break;
            }
        }

        foreach (decimal EachVal in ValList.OrderByDescending(pX => pX)) {
            if (EachVal <= mR) {
                mR = EachVal;
                break;
            }
        }

        Console.WriteLine((mR - mL) / mM + 1);
    }

    // 前後のListを返す
    static List<decimal> DeriveValList(decimal pVal)
    {
        var WillReturn = new List<decimal>();

        decimal Mod = pVal % mM;
        decimal BaseVal = pVal - Mod;

        for (int I = -3; I <= 3; I++) {
            WillReturn.Add(BaseVal + I * mM);
        }
        return WillReturn;
    }
}

解説

オーバフロー対策で、long型ではなくdecimal型を使うようにします。

数直線で考えれば、
A,L,Rを、Aが原点になるように平行移動させ、
クリスマスツリーがあるのは、Mの倍数の座標だと考えれば良いと分かります。

後は、LとRに対し、
M割った余りを引いて、前後のMの倍数を求めて、ListにAddし、
Lの最小上界と、Rの最大下界
を求めれば、解くことができます。