Kazun の競プロ記録

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

AtCoder Beginner Contest 274 C問題 Ameba

AtCoder ABC274 ABC C問題 300 pts

問題

提出解答

問題の概要

アメーバ $1$ がいる. $1 \leq t \leq N$ となる整数 $t$ において, $t$ 秒後に次のことが起こった.

アメーバ $A_t$ が分裂し, アメーバ $2t, (2t+1)$ が誕生した.

アメーバ $A_t$ をアメーバ $2t, (2t+1)$ の親と呼ぶとき, $1$ 以上 $(2N+1)$ 以下の整数 $i$ それぞれに対してアメーバ $i$ から何世代親を遡るとアメーバ $1$ になるか?

制約

$1 \leq N \leq 2 \times 10^5$
$1 \leq A_t \leq 2t-1$
$A_t$ は相異なる整数

解法

求めるべき解答を $X_i$ とする. $u_i:=\left \lfloor \dfrac{i-1}{2} \right \rfloor$ *1 と, $i=1,2, \dots, 2N+1$ に対して以下が成り立つ.

$X_i=\begin{cases} 0 & (i=1) \\ X_{A_{u_i}}+1 & (i \neq 1) \end{cases}$

よって, これを $i=1,2, \dots, 2N+1$ の順に求められば全てを $O(N)$ 時間で求めることが出来る.

*1:アメーバ $i$ が誕生した時刻