AtCoder Beginner Contest 247 C問題 1 2 1 3 1 2 1

整数の列の列 $S_1, S_2, \dots$ を以下で定める.

$S_N$ を求めよ.

$S$ に関する漸化式が与えられているので, この漸化式を利用して再帰的に求めることができる.

また, $S_{n+1}$ の計算においては $S_n$ から求められるので, for 文でも簡単に求められる.

$S_n$ の項の数は $2^n-1$ である. このとき, $S_n$ の第 $i$ 項 $S_{n,i}$ は

$\displaystyle S_{n,i}=\begin{cases} S_{n-1,i} & (i \leq 2^{n-1}-1) \\ n & (i=2^n) \\ S_{n-1, i-2^{n-1}} & (2^n+1 \leq i) \end{cases}$

である.

このとき, $i \leq 2^n-1$ ならば, $S_{n,i}$ は $i$ によって決定されることに注目する. 実は, $S_{n,i}$ は ( $i$ を $2$ で割り切る回数) $+1$ と一致する.

Kazun の競プロ記録