Kazun の競プロ記録

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

AtCoder Regular Contest 161 B問題 Exactly Three Bits

AtCoder ARC ARC161 B問題 400 pts

問題
提出解答
問題の概要
- 制約
解法

問題

提出解答

(※ C++ での提出) atcoder.jp

問題の概要

$N$ 以下の正の整数 $X$ で以下を満たすものは存在するか? 存在するならばそのような整数のうちの最大値を求めよ.

$X$ を $2$ 進法表記したときに現れる $1$ の個数がちょうど $3$ である.

$T$ 個のマルチテストケース

制約

$1 \leq T \leq 10^5$
$1 \leq N \leq 10^{18}$

解法

条件を満たす $X$ のうち, 最小の正の整数は $X=7$ なので, $N \lt 7$ の範囲では存在しないとなる.

以降では $N \geq 7$ とする.

$g(N,k)$ を $N$ 以下の非負整数で, $2$ 進法表記したときに現れる $1$ の個数がちょうど $k$ であるような非負整数のうち, 最大であるようなものと定義する (存在しない場合は $-\infty$ ).

このとき, 次のようにして場合分けすることによって, 帰納的に導くことができる.

$N=0$ の場合, $0$ 以下の正の整数は存在しないので, $g(0,k)=-\infty$ である.
$k=1$ の場合, $a$ を $2^a \leq N \lt 2^{a+1}$ 以下を満たす整数として, $g(N,1)=2^a$ である.
$N$ が奇数のとき, $1$ の位をどうするかで場合分けすることにより, $g(N,k)=\max(2g(\frac{N-1}{2}, k-1)+1, 2(\frac{N-1}{2}, k))$ となる.
$N$ が偶数のとき, $1$ の位をどうするかで場合分けすることにより, $g(N,k)=\max(2g(\frac{N}{2}-1, k-1)+1, 2(\frac{N}{2}, k))$ となる.

これにより, 求めるべきは $g(N,3)$ である. また, $g(N,k)$ に出てくる引数の候補は $O(\log N)$ 個であるので, $g(N,3)$ を $O((\log N)^2)$ 時間で求めることができる.

これは $T$ 個のテストケースの下では, 高速な言語を使用することによって, 正解することができる.