Kazun の競プロ記録

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

AtCoder Beginner Contest 236 B 問題 Who is missing?

AtCoder ABC ABC236 B問題 200 pts

問題

提出解答

問題の概要

$1,2,\dots, N$ と書かれたカードが $4$ 枚ずつ, 合計 $4N$ 枚ある.

この中から $1$ 枚抜き出した.

残りの $4N-1$ 枚に書かれている整数は $A_1, \dots, A_{4N-1}$ である.

抜き出したカードに書かれている整数は何か?

制約

$1 \leq N \leq 10^5$
$1 \leq A_i \leq N$
$k=1,2, \dots, N$ に対して, $A_i=k$ となる $i$ は $4$ 個以下

解法

$A_1, \dots, A_{4N_1}$ の中にある $k$ の個数を $X_k$ とする. このとき, 抜き出した整数 $l$ は $X_l=3$ を満たす.

よって, $X_k$ を求めた後, $X_l=3$ となる $l$ を求めれば良い.

なお, 制約からこのような整数 $l$ は一意に存在する.