けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AtCoder AGC 017 B - Moderate Differences (青色, 400 点)

むむむ

問題へのリンク

問題概要

長さ  N の整数列  x_1, x_2, \dots, x_N であって、

  •  x_1 = A
  •  x_N = B
  •  |x_{i} - x_{i+1}| C 以上  D 以下の整数

となるものが存在するかどうかを判定せよ。

制約

  •  3 \le N \le 5 \times 10^{5}

考えたこと

とりあえず  x_1 = 0,  x_N = |A - B| としてよい。

さて、 0 からスタートして、 N ターン目にどんなのを作れるかを考察してみる。

  • 1 ターン目:[-D, -C], [C, D] が作れる
  • 2 ターン目:[-2D, -2C], [C-D, -C+D], [2C, 2D] が作れる
  • 3 ターン目:[-3D, -3C], [C-2D, -2C+D], [2C-D, -C+2D], [3C, 3D] が作れる

という感じになっていて、3 ターン目の式をみると「長さ  3(C-D)区間が等間隔に 4 つ並んでいる」という感じの式になっている (この 4 区間がオーバーラップすることはありうる)。

一般に  n ターン後は「長さ  n(C-D)区間が等間隔に  n+1 個並んでいる」という状態になることがわかる。

したがって、 N-1 ターン後に  |A-B| がある区間内に存在しているかどうかは  O(N) で判定できることになる。

#include <iostream>
#include <cmath>
using namespace std;

long long N, A, B, C, D;
int main() {
    cin >> N >> A >> B >> C >> D;
    A *= 2, B *= 2, C *= 2, D *= 2;
    --N;
    long long diff = abs(A - B);
    long long gap = (C + D) / 2;
    long long center = 0;
    if (N & 1) center = gap;
    long long radius = (D - C) / 2 * N;

    bool ok = false;
    for (int i = 0; i < N*2; ++i) {
        long long left = center - radius, right = center + radius;
        if (right > D * N) break;
        if (left <= diff && diff <= right) ok = true;
        center += gap * 2;
    }
    if (ok) cout << "YES" << endl;
    else cout << "NO" << endl;
}