AtCoder Grand Contest 017 B - Moderate Differences

問題

 N個のマスが一列に並んでおり、一番左には整数A、一番右にはBが書き込まれているとする。どの隣接マスについても書かれている整数の差がC以上D以下であるように残りのマスを埋めることができるかどうか判定せよ。

解法

 Aから+[C, D]または-[C,D]のような操作をN - 1回行ったときBになるかどうかを考える。i回足す操作をすると残りのN - 1 - i回は引く操作をすることになり、それぞれ変動量の絶対値が大きくなるのは毎回Dを足し引きするとき、小さくなるのはCを足し引きするとき。最大と最小の間は足す量引く量を調節すれば自由に取れるので、結局
 \displaystyle A + i C - (N - 1 - i) D \le B \le A + i D - (N - 1 - i) C
i = 0, 1, \dots, N - 1のどれかで満たされていればいい。

 解説PDFも同じ。

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

int main() {
    ll N, A, B, C, D;
    cin >> N >> A >> B >> C >> D;

    for (ll i = 0; i < N; i++) {
        //i回は大きくなり,N - 1 - i回は小さくなる
        ll max = A + i * D - (N - 1 - i) * C;
        ll min = A + i * C - (N - 1 - i) * D;
        if (min <= B && B <= max) {
            cout << "YES" << endl;
            return 0;
        }
    }

    cout << "NO" << endl;
}

反省

 14分ちょいでAC。図を書いていたら足す回数、引く回数に着目する発想が出てきて、その後はすぐに解けた。こういうある操作の回数をiとして~という考え方はよくあるので重要だと思う。

 以下は考察中のメモ。右下で足す回数をxとしてやれば良さそうということに気づいている。それまでの図が有効だったかどうかは……わからない。

f:id:tokumini:20180730101202p:plain