AGC029 B - Powers of two - ツバサの備忘録

解法

実は貪欲法です。
大きい数字から、ペアを決めていきます。
ペアのうち大きい数字を $x$ とし、もう片方を $y$ とします。すると、 $x$ と $y$ で作ることができる2べきの数は、1種類しか存在しません。
$x$ より大きい2べきの数のうち最小のものを $z$ とすると、 $x \geqq z-x$ ですが(式変形すると $x \geqq z/2$ となります、設定した条件を満たしています)、 $z$ の次に小さい2べきの数は $2z$ であるため、 $x \lt 2z - x$ となってしまいます(式変形すると $x \lt z$ となります、こちらも設定した条件通りです)。

よって、1種類しか存在しないのなら、そのペアは真っ先に選択すべきです。
これは以下のようにして背理法によって証明されます(間違っていたらごめんなさい)。
今、 $x,y$ の和が2べきになるとします。 $x \geqq y$ です。
そして、 $x$ 以下の数字のみが存在する集合 $S$ が存在して、 $\{x,y,S \}$ の中でのペアの最大数を考えることにします。
$S$ の中で作れるペアの最大数を $k$ とすると、 $(x,y)$ をペアとした時は、 $k+1$ が答えとなります。
さて、ここで $(x,y)$ のペアを選ばない方が全体の最大数が多くなると仮定します。すると、 $x$ は $y$ 以外でペアを作れる数字が存在しない(厳密には $S$ の元として $y$ がある可能性がありますが、状況は今のまま変わらないため除外します)ので、 $\{y,S \}$ の中で2べきのペアの個数が $k+2$ 以上となることになります。
こうなるためには、 $S$ の中で、少なくともペアの個数が $k+1$ になっていなければなりません。なぜならば、 $y$ とのペアを1つ作成しても個数はもちろん1つにしかならないので、 $k+2$ となるには、残りの $k+1$ つのペアを $S$ でカバーしきらなければならないからです。
これは、 $S$ のペアの最大数が $k$ であることと矛盾します。
ということは、そもそも $(x,y)$ のペアを選ばない方が全体の最大数が多くなるという仮定が間違っていたことになるので、 $(x,y)$ を選んだ場合の、 $k+1$ 個が答えの最大値となります。
というわけで、結局数列 $A$ を降順でソートし、大きい数字から順番に、2べきをつくれるような相方が存在すればペアを作り…ということを繰り返していけば、最終的なペアの個数が求まります。