AGC029 B. Powers of two - phyllo’s algorithm note

問題

N個のボールがあり、i番目のボールには正の整数A_iが書かれている。
このとき、2つのボールを取り出してペアを作り、その数字の和が2ベキ(2^t)になっている場合、そのペアを取り除くことができる。
最大で何回ペアを取り除くことができるか？

制約

1 <= N <= 2 * 10^5
1 <= A_i <= 10^9

解法

大きい数字の方から注目すると、自身よりも小さい数字でペアを作ることになる場合、2ベキになる数字は一意に決まる(自身より大きい一番小さい2ベキになる)。

ある数字xについて、その数字以下のペアになれる数字yが存在する場合、「xを除いた集合」で「xとyを除いた集合」よりもペアを多く作れないならxとyでペアを作っておいたほうがよいが、ペア数は同数か少なくなるしかないので、結局ペアを作っておいたほうが良い。
したがって、greedyに、大きい方の数字からペアを作れたら取り除く、を繰り返していけば求められる。

c++の場合はmultisetで検索、削除などを簡単に実装できる。

  multiset<int> m;
  rep(i, N) {
    int a;
    cin >> a;
    m.insert(a);
  }
 
  int ret = 0;
 
  while (!m.empty()) {
    int x = *(m.rbegin()); //大きい数字から処理
    m.erase(m.find(x)); //(m.erase(x)にしてしまうと値xがすべて消えてしまう)
 
    ll p = 1;
    while (p <= x) p *= 2;
    int y = p - x; //ペアになれる数字は一意に決まる
 
    if (m.find(y) != m.end()) {
      m.erase(m.find(y));
      ret++;
    }
  }
 
  cout << ret << endl;

解法2

上記の解法の考察がやや自分の感覚では自身なかったので、もうちょっと無駄なことを本番では考えてた。

同じ数字のボールをまとめ上げた(数字, 個数)で考える。これをノードとみなす。
大きい数字のペアをその数字より小さい数字で作る場合は一意に決まることから、大きい数字のノードから小さい数字へのノードに辺を貼ると、これは森になっている。

ある木について考えると、ペアをできるだけ作ることを考えると、葉ノード側からできるだけペアを作るのがいいので、葉ノード側から処理してペアを作る。
最後に、2ベキな数字で残っているボールがある場合、同じ数字でペアが作れるので、それを加えれば答えが求められる。

反省

勉強不足と考察不足。ついでに実装の仕方がダメダメだった。
本番は、2ベキなボールは同じ値でしかペアになれない(嘘)、と思い違いして最初にコーナーケース的処理を入れてしてしまっていて通せなかった。。
すぐに反例が思いつくのに、間違っていないと思っている考察に対して疑うのは難しい・・・

greedy法の証明は典型らしいかも？(帰納的に考える)
「今、操作xをしなかった場合、残りの部分で操作xした場合よりスコアが高くならないならば、今、操作xをしたほうがよい」