「変数を固定する考え方」と「set の活用」を組み合わせる練習問題！

問題へのリンク

問題概要

整数 $K$ と、 $N$ 個の整数 $A_{1}, A_{2}, \dots, A_{N}$ が与えられる。

$A_{i} - A_{j} = K$

を満たす [tex i, j] ( $i = j$ でもよい) が存在するかを判定せよ。

制約

$2 \le N \le 2 \times 10^{5}$
$-10^{9} \le K, A_{i} \le 10^{9}$

考えたこと

この問題のように、 $i, j$ という 2 つの変数を考える必要のある問題では、一方を固定すると良いことが多い！

ここでは、 $i$ を固定してみよう（ $j$ を固定しても解ける）。そうすると、次のような問題となる。

$A_{j} = A_{i} - K$

を満たすような $j$ が存在するかどうかを判定せよ。

これは、整数 $A_{1}, A_{2}, \dots, A_{N}$ を格納した集合（C++ ならば set 型）を用意しておけば、

「集合に $A_{i} - K$ が含まれているかどうかを判定する」

ことによって解ける。この判定の計算量は $O(\log N)$ であるため、 $i = 1, 2, \dots, N$ に対して判定すると、判定全体の計算量は $O(N \log N)$ となる。

また、集合を作る部分についても、1 つ 1 つの要素を挿入するのに $O(\log N)$ の計算量を要することから、集合を作る部分全体の計算量も $O(N \log N)$ となる。

以上より、全体を通して、 $O(N \log N)$ の計算量の解法が得られた。

コード

#include <bits/stdc++.h>
using namespace std;

int main() {
    int N, X;
    cin >> N >> X;
    vector<int> A(N);
    set<int> S;
    for (int i = 0; i < N; i++) {
        cin >> A[i];
        S.insert(A[i]);
    }

    // i を固定して判定
    for (int i = 0; i < N; i++) {
        if (S.count(A[i] - X)) {
            cout << "Yes" << endl;
            return 0;
        }
    }
    cout << "No" << endl;
}

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

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

AtCoder ABC 296 C - Gap Existence (4Q, 灰色, 300 点)

問題概要

制約

考えたこと

コード