Kazun の競プロ記録

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

AtCoder Beginner Contest 234 C 問題 Happy New Year!

AtCoder ABC ABC234 C問題 300 pts

問題

提出解答

問題の概要

$10$ 進法において $0,2$ からなる正の整数のうち, $K$ 番目に小さいものを正確に求めよ.

制約

$1 \leq K \leq 10^{18}$

解法

問題文の $2$ を $1$ に置き換えると, その問題文は, 「 $K$ の2進表記を求めよ」と等価になることがわかる.

よって, $K$ の2進表記を求め, $1$ の代わりに $2$ を出力すれば正解となる.

計算量は $O(\log K)$ である.