Kazun の競プロ記録

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

AtCoder Beginner Contest 293 B問題 Call the ID Number

AtCoder ABC293 ABC 200 pts B問題

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

問題

提出解答

問題の概要

$N$ 人がいる. この人たちは人 $1$ , 人 $2$ , $\dots$ , 人 $N$ と名付けられている.

$i=1,2, \dots, N$ の順に以下を実行する.

人 $i$ 自身の番号が $1$ 回も呼ばれていないならば, 人 $A_i$ の名前を叫ぶ.

最後まで呼ばれない人を全員求めよ.

制約

$1 \leq N \leq 2 \times 10^5$
$1 \leq A_i \leq N$
$A_i \neq i$

解法

人 $i$ が呼ばれているかどうかを記録する配列を用意し, 実際にその配列を確認しながら, 呼ぶ際にはその配列を更新していけばよい.