Atcoder AGC 017 B. Moderate Differences

Atcoder AGC 017 B. Moderate Differences

B: Moderate Differences - AtCoder Grand Contest 017 | AtCoder

解法

数列において減少する回数を固定して、差分($\ B - A\ $)のとりうる最小最大を決めて条件を満たすものがあるかを判定する。

例えば下限を考えているときは、増加させる際に最低$\ C\ $だけ増加させる必要があり、減少させる際に$\ D\ $だけ減少させることができるので、これで下限が求められる。

こうして求めた下限、上限の間の任意の数をとれることは言うまでもない。

このように回数を固定して考える発想は常に持っておきたい。

実装

#include "bits/stdc++.h"
using namespace std;

int main() {
        long long n, a, b, c, d; cin >> n >> a >> b >> c >> d;
        bool ans = false;
        for (int i = 0; i < n - 1; i ++) if (i * c - (n - 1 - i) * d <= b - a && b - a <= i * d - (n - 1 - i) * c) ans = true;
        cout << (ans ? "YES" : "NO") << endl;
        return 0;
}