AGC-017-B Moderate Differences

■■■問題■■■

N個のマスが一列に並んでいます。
一番左のマスには整数Aが、一番右のマスには整数Bが書かれており、他のマスには何も書かれていません。

青橋君は、何も書かれていないマスに整数を書き込み、次の条件を満たすようにしたいです：
●どの隣接する2マスについても、書かれている整数の差はC以上D以下である。

青橋君は、この条件を満たす限り、いくらでも大きい整数や小さい整数を書き込むことができます。
青橋君が条件を満たすように整数を書き込むことができるかを判定してください。

■■■入力■■■

N A B C D

●3 <= N <= 50万
●0 <= A <= 10の9乗
●0 <= B <= 10の9乗
●0 <= C <= D <= 10の9乗
●入力はすべて整数

■■■出力■■■

青橋君が条件を満たすように整数を書き込むことができるならYESを、できないならNOを出力せよ。

C#のソース

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static string InputPattern = "Input1";

    static List<string> GetInputList()
    {
        var WillReturn = new List<string>();

        if (InputPattern == "Input1") {
            WillReturn.Add("5 1 5 2 4");
            //YES
            //例えば、左のマスから順に 1,-1,3,7,5 となるように整数を書き込めばよいです
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("4 7 6 4 5");
            //NO
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("48792 105960835 681218449 90629745 90632170");
            //NO
        }
        else if (InputPattern == "Input4") {
            WillReturn.Add("491995 412925347 825318103 59999126 59999339");
            //YES
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static void Main()
    {
        List<string> InputList = GetInputList();
        long[] wkArr = InputList[0].Split(' ').Select(X => long.Parse(X)).ToArray();
        long N = wkArr[0];
        long A = wkArr[1];
        long B = wkArr[2];
        long C = wkArr[3];
        long D = wkArr[4];

        bool IsOK = false;

        //+の数でループ
        for (int I = 0; I <= N - 2; I++) {
            long MinusCnt = N - 1 - I;

            long MinVal = A + C * I - D * MinusCnt;
            long MaxVal = A + D * I - C * MinusCnt;

            Console.WriteLine("+が{0}個で、-が{1}個での最小値={2}", I, MinusCnt, MinVal);
            Console.WriteLine("+が{0}個で、-が{1}個での最大値={2}", I, MinusCnt, MaxVal);

            if (MinVal <= B && B <= MaxVal) {
                IsOK = true;
                break;
            }
        }
        Console.WriteLine(IsOK ? "YES" : "NO");
    }
}

デバッグ情報付の実行結果

+が0個で、-が4個での最小値=-15
+が0個で、-が4個での最大値=-7
+が1個で、-が3個での最小値=-9
+が1個で、-が3個での最大値=-1
+が2個で、-が2個での最小値=-3
+が2個で、-が2個での最大値=5
YES

解説

足し算の交換法則をふまえ、

値を増やす回数と、値を減らす回数の組合せを全探索して、
変化後の最小値から変化後の最大値の間に、Bがあるかを判定してます。