問題
個のマスが一列に並んでおり、一番左には整数、一番右にはが書き込まれているとする。どの隣接マスについても書かれている整数の差が以上以下であるように残りのマスを埋めることができるかどうか判定せよ。
解法
から]または]のような操作を回行ったときになるかどうかを考える。回足す操作をすると残りの回は引く操作をすることになり、それぞれ変動量の絶対値が大きくなるのは毎回を足し引きするとき、小さくなるのはを足し引きするとき。最大と最小の間は足す量引く量を調節すれば自由に取れるので、結局
がのどれかで満たされていればいい。
解説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。図を書いていたら足す回数、引く回数に着目する発想が出てきて、その後はすぐに解けた。こういうある操作の回数をとして~という考え方はよくあるので重要だと思う。
以下は考察中のメモ。右下で足す回数をとしてやれば良さそうということに気づいている。それまでの図が有効だったかどうかは……わからない。