AtCoder Beginner Contest 281 F問題 Xor Minimization
問題
提出解答
問題の概要
個の非負整数
が与えられる. 次の値を求めよ.
ただし, を非負整数全体の集合とする.
制約
解法
非負整数列 に対するこの問題の答えを
と書くことにする.
の2進表記における最大の桁数を
とする. このとき, 次がわかる. なお, この
の定め方から,
の中に
の位が
である整数が存在することに注意する.
の
の位が全て
だった場合
の場合を考慮することによって,
であることが分かる. また, XOR における桁ごとの独立性から,
の
の位を
にした整数を
としたとき,
である.
の
の位が全て
ではない場合
どのような を選んでも,
の
の位が
であるような整数
及び,
であるような整数
が存在することから,
であることがわかる.
ここで, 議論のために の
の位が
,
の
の位が
であるとしても問題ない.
の
の位を
にした整数を
とする. このとき, 次の2パターンを考えることになる.
の
の位を
にするような整数
においては
の
の位が
になる. XOR の桁ごとの独立性から,
に帰着することができる.
の
の位を
にするような整数
においては
の
の位が
になる. XOR の桁ごとの独立性から,
に帰着することができる.
よって,
である.
これにより, 1回行うごとに, 最高位が になることから, 高々
回の再帰で正解を求めることができる. 従って,
時間で求められることになる.