Codeforces Round #486 (Div. 3) D. Points and Powers of Two

問題概要

数直線上の $n$ 個の点 $x_1, \cdots, x_n$ が与えられる. この中から適当な個数の点を選び, 選んだ点を $x_{i_1}, \cdots, x_{i_k}$ としたとき任意のペアについて $|x_{i_a} - x_{i_b}|$ が $2$ の累乗になるようにしたい. このとき, 最大何個の点を選ぶことができるか？構成とともに示せ.

制約

$1 \le n \le 2\times 10^5$
$-10^9 \le x_i \le 10^9$

解法

明らかに $1$ 点のみを選ぶことは可能です. また, $2$ 点選ぶのも, ある点 $x_i$ に対して選びうる点は $x_i \pm 2^d$ だけですから適当な $d$ の範囲について対応する点が存在するかどうかを判定すれば良いです.

$3$ 点選ぶ時の条件は何でしょうか？ $x_a \lt x_b \lt x_c$ なる三点を選ぶとき, $x_b - x_a = x_c - x_b = 2^d$ を満たすことが必要です. もし $x_b - x_a \neq x_c - x_b$ となるなら, $x_c - x_a$ は少なくとも二つの bit が立ってしまいます(二進数で考えるとわかりやすいです). この判定も候補が定数個なので適切に実装すれば実行時間制限以内に解が存在することを確かめることができます.

$4$ 点以上選ぶのは明らかに不可能です. $x_a \lt x_b \lt x_c \lt x_d$ を選ぶならば, $3$ 点の時の議論から $x_b - x_a = x_c - x_b = x_d - x_c = 2^d$ がなりたたければなりませんが, このとき $x_d - x_a$ は明らかに $3$ の倍数になってしまいます.

以上より, 確かめる解の大きさの最大値は $3$ なので, その部分を全探索すれば良いです.

実装

解の上限が大きさ $3$ だとあらかじめわかっているので, $3$ の解があればそれをすぐに出力しています.

Submission #146217002 - Codeforces