Kazun の競プロ記録

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

AtCoder Regular Contest 139 A問題 Trailing Zeros

AtCoder ARC ARC139 A問題 300 pts

問題

提出解答

問題の概要

正の整数 $x$ に対して, $x$ を2進表記した際に末尾に連続する $0$ の数を $\operatorname{ctz}(x)$ と書くことにする.

次を満たす長さ $N$ の正の整数列 $A=(A_1, \dots, A_N)$ において, $A_N$ の最小値を求めよ.

$A$ は狭義単調増加
$A_i=T_i$

制約

$1 \leq N \leq 10^5$
$0 \leq T_i \leq 40$

解法

正の整数 $x$ と非負整数 $t$ に対して, 以下は同値である.

$\operatorname{ctz}(x)=t$
$x$ を $2^{t+1}$ で割った余りが $2^t$ である.

実は, 次のようにして構成される $B=(B_1, \dots, B_N)$ が末項の最小値を実現する. ただし, 説明の都合上, $B_0=0$ とする.

$B_i$ を $B_{i-1}$ より大きく, $2^{T_{i+1}}$ で割った余りが $2^{T_i}$ であるような整数の最小値とする.

$B$ の末項が最小値になることは, $B$ の構成方法が, 条件を満たすような整数のうちの最小値を採用していることから従う.

以上から, 時間計算量 $O(N)$ で求めることができた.