Kazun の競プロ記録

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

AtCoder Beginner Contest 243 D問題 Moves on Binary Tree

AtCoder ABC ABC243 D問題 400 pts

問題

提出解答

問題の概要

$S:=2^{10^{100}}-1$ 頂点からなる完全二分木があり, $S$ 個の頂点にはそれぞれ $1,2, \dots, S$ と名付けられている.

ここで, この二分木は以下のようにして構成されている.

$i=1,2, \dots, 2^{10^{100}-1}$ に対して, 頂点 $i$ の左の子, 右の子はそれぞれ $2i, 2i+1$ である.

最初, 頂点 $X$ がマークされており, このマークは $j$ 回目の移動では

$S[j]={\tt U}$ ならば今いる頂点の親に移動する.
$S[j]={\tt L}$ ならば今いる頂点の左の子に移動する.
$S[j]={\tt R}$ ならば今いる頂点の右の子に移動する.

$N$ 回目の移動後にマークされている頂点の番号 $Y$ を答えよ. ただし, $Y \leq 10^{18}$ になるような入力のみ与えられる.

制約

$1 \leq N \leq 10^6$
$1 \leq X \leq 10^{18}$
$S$ は ${\tt U}, {\tt L}, {\tt R}$ からなる長さ $N$ の文字列.
$S$ は可能な移動を表す.
$Y \leq 10^{18}$ になる.

解法

番号を2進数で表すと各移動を頂点番号には以下のような関係が生まれる.

上に移動することは, 番号の2進表記の末尾を削除することに対応する.
左の子に移動することは, 番号の2進表記の末尾に $0$ を加えることに対応する.
右の子に移動することは, 番号の2進表記の末尾に $1$ を加えることに対応する.

2進表記について, Queue で記録することにより, $Y$ を $O(N+ \log X+\log Y)$ で求める事ができる.