Kazun の競プロ記録

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

AtCoder Beginner Contest 243 B問題 Hit and Blow

AtCoder ABC ABC243 B問題 200 pts

問題

提出解答

問題の概要

各項が異なる長さ $N$ の整数列の $A,B$ が与えられる. 以下を満たす整数の個数をそれぞれ求めよ.

$A,B$ に共通して存在し, その場所も一致する整数
$A,B$ に共通して存在するが, その場所は異なる整数

制約

$1 \leq N \leq 1000$
$1 \leq A_i, B_j \leq 10^9$
$A_1, \dots, A_N$ は全て異なる
$B_1, \dots, B_N$ は全て異なる

解法

共通して存在する整数の候補は $A_1, \dots, A_N$ の $N$ 個である.

それぞれの $A_i$ に対して, $A_i$ が $B$ に存在するか? 存在するならばその場所はどこか? ということを各 $A_i$ に対して計算量 $O(N)$ で求められる.

これを $A_1, \dots, A_N$ ごとに見ることにより, 求めるべき個数を時間計算量 [tex: O(N²)] で求めることができる.