Kazun の競プロ記録

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

AtCoder Beginner Contest 263 B問題 Ancestor

AtCoder ABC ABC263 B問題 200 pts

問題

提出解答

問題の概要

$N$ 人の人がいる. この $N$ 人を人 $1, \dots,$ 人 $N$ と呼ぶことにする. $i=2,3, \dots, N$ に対して, 人 $i$ の親は人 $P_i$ である. ただし, $P_i \lt i$ が成り立つ. 人 $N$ から見ると, 人 $1$ は何代前か?

制約

$2 \leq N \leq 50$
$1 \leq P_i \lt i$

解法

次のアルゴリズムによって正解できる.

$X \gets 0$ とする.
以下の操作を繰り返し続ける.
- $i=1$ ならば $X$ を出力し, アルゴリズムを終了させる.
- $i \neq P_i$ ならば, $i \gets P_i$ とする.

このアルゴリズムにおいて, 答えは $N$ 以下であるから計算量は $O(N)$ である.