むむむ

問題概要

長さ $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;
}

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

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

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

問題概要

制約

考えたこと