AGC029B Powers of two
問題概要
N個の要素がある。
1 <= N <= 2*10^5
1 <= 要素 <= 10^9
足して2べきになれる要素はペアになれる。
最大いくつのペアができるか。
考察
1のペアだけでいくつあるねん...。
1, 3, 7, 15, 31, ...
実は、ある要素Xの、Xより小さいペアは1通りしか存在しないのでは？
例えば31の自身以下のペアは1のみ。
検討1
X+Y=Zで、Zは2べきの時、X+Y'=2ZとなるY'は1 ~Xの範囲か？
Y'=2Y+X>XなのでY'は範囲外。
検討2
X+Y=2Zで、2Zは2べきの時、X+Y''=ZとなるY''は1 ~Xの範囲か？
Y''=(Y-X)/2<=0なのでY''は範囲外。
検討より、ある要素Xの、Xより小さいペアは1通りしか存在しなさそう。
この検討が十分なのか、そもそも怪しい。
大きい要素から貪欲に使って行けば無駄がなさそう。
提出
→AC
やったぜ。
