Kazun の競プロ記録

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

AtCoder Beginner Contest 269 C問題 Submask

AtCoder ABC269 ABC C問題 300 pts

問題

提出解答

問題の概要

以下の条件を全て満たす非負整数 $x$ を昇順に全て列挙せよ.

$N,x$ の2進数表記において, 任意の非負整数 $k$ で $x$ の $2^k$ の位が $1$ ならば, $N$ の $2^k$ の位も $1$ である.

制約

$0 \leq N \lt 2^{60}$
$N$ の $2$ 進数表記において, $1$ である位の数は $15$ 個以下.

解法1

$N$ の $2^k$ の位が $0$ ならば, $x$ の $2^k$ の位も $0$ でなくてはならない. これから, $N$ の2進数表記において, $1$ である位のみを $x$ において動かせば条件を満たす整数が作れる. また, これによってが条件を満たす整数を全て列挙できる,

よって, $N$ の $2^k$ の位が $1$ であるような $k$ を $k_1, \dots, k_K$ とする $(K \leq 15)$ . このとき, $x$ において, 各 $2^{k_i}$ の位を $0$ にするか $1$ にするかを bit 全探索その方法を列挙することによって, 条件を満たす $x$ を全て列挙することができるので, これを昇順に並び替えれば良い.

計算量は $O(\log N+K 2^K)$ である.

解法2

実は, 以下の疑似アルゴリズムで条件をみたす $x$ を降順に全て列挙できる.

$S \gets N$
$A \gets$ (空リスト)
$S \gt 0$ である限り, 以下を繰り返す: $A$ に $S$ を加えたあと, $S \gets N \land (S-1)$ *1.
$A$ に $0$ を加える.

問題文では昇順に列挙することを要求されているので, 反転を忘れないこと.

*1: 非負整数 $x,y$ に対して, $x \land y$ で $x,y$ の bitwise and を表す