AGC029 B - Powers of two

問題
提出コード

解法

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

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