Moderate Differences [AtCoder Grand Contest 017 B]

http://agc017.contest.atcoder.jp/tasks/agc017_b

解法

http://agc017.contest.atcoder.jp/submissions/1413391

まず、N要素あるということは、N-1回操作を行って差を埋めていけばいい。
差は大きい小さいというのは問題ではないので、d=abs(A-B)として、dだけ差分を詰めたいと考える。

さて、[C,D]だけ増やすことができるので、最大で考えると、[C*(N-1),D*(N-1)]だけの差分を網羅できると分かる。
しかし、これでは増やして減らすなどの更新が行えない。
1回分増やして減らすことで[0,D-C]の範囲で微調整が加えてできる。

さて、ここで[0,D-C]の範囲での微調整の回数を全探索して考えてみる。
微調整をi回行ったとすると、回数としては、i*2回必要なため、[C,D]で増やすのを考えると、[C*(N-1-i*2),D*(N-1-i*2)]の差分を網羅できる。
それに微調整i回分[0,(D-C)*i]を考えると、網羅できる差分は[C*(N-1-i*2)-(D-C)*i,D*(N-1-i*2)+(D-C)*i]となり、ここに差分
dが含まれていればいい。

微調整の回数を全探索するのは計算量的にも問題ないので、AC

#define NO "NO"
#define YES "YES"
typedef long long ll;
//---------------------------------------------------------------------------------------------------
ll N, A, B, C, D;
string solve() {
    ll d = abs(A - B);
 
    ll i = 0LL;
    while (i * 2LL <= N - 1LL) {
        ll ma = D * (N - 1LL - i * 2LL);
        ll mi = C * (N - 1LL - i * 2LL);
 
        ll mma = abs(C - D) * i;
 
        if (mi - mma <= d && d <= ma + mma) return YES;
 
        i++;
    }
    return NO;
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> A >> B >> C >> D;
    cout << solve() << endl;
}