Kazun の競プロ記録

競技プログラミングに関する様々な話題を執筆します.

AtCoder Beginner Contest 296 C問題 Gap Existence

AtCoder ABC ABC296 C問題 300 pts

問題
提出解答
問題の概要
- 制約
解法

問題

提出解答

問題の概要

$N$ 個の整数 $A_1, \dots, A_N$ に対して, 以下を満たす整数の組 $(i,j)$ は存在するか?

$1 \leq i,j \leq N$
$A_i-A_j=X$

制約

$2 \leq N \leq 2 \times 10^5$
$-10^9 \leq A_i \leq 10^9$
$-10^9 \leq X \leq 10^9$

解法

$j=k$ であるような条件を満たすような $(i,j)$ が存在することと, $X+A_k$ が $A$ に存在することは同値になる.

よって, これを $k=1,2, \dots, N$ に対して行い, 「 $X+A_k$ が $A$ に存在する」ことが成り立つ $k$ が存在するかどうかで判定すれば良い.

ここで, どのような $k$ においても, 存在判定において, $A$ をリストで持ったまま行ってしまうと, $1$ 回あたり $\Theta(N)$ 時間で, 合計 $\Theta(N^2)$ 時間かかってしまい, 間に合わない.

しかし, $A$ を集合のデータ構造で持つことにより, $1$ 回あたり $O(1)$ 時間または $O(\log N)$ 時間 (言語等による) で実行でき, 合計で $O(N), O(N \log N)$ 時間となることから十分高速である.