B - Powers of two

Quiz

https://atcoder.jp/contests/agc029/tasks/agc029_b

AC code

https://atcoder.jp/contests/agc029/submissions/13113984

解説

f:id:peroon:20200511150414p:plain

  • A = 3,1,1,5 を考えてみる
  • 左から見ていって2べきになれるペアに貪欲にくっつけるのはNGだと分かる
  • A = 3,1,7,5 を考えてみる
  • Aをソートして、左から見ていってペアにできるならペアにする貪欲、これもNGだと分かる
  • グラフを書いてみて次数を見ると、大きい値の方が次数が少ない。ペアになれる候補が少ないから
  • 条件が厳しい方からくっつけていく方がより多くのペアが作れそう
  • 大きい値から見て、2べきになれるペアがあればそれを貪欲に採用、これが答え

学び

  • ソートして貪欲を検討するなら、降順ソートして貪欲も考えてみよ

code

  • multisetを使ってみた
ll f(ll a){
  ll v = 1;
  while(a>v){
    v *= 2;
  }

  // aが2べき
  if(v-a==0){
    return a;
  }
  // それ以外
  else{
    return v-a;
  }
}

int main(){
    // input
    ll N; 
    cin>>N;

    multiset<ll> se;
    rep(i,N){
      ll a;cin>>a;
      se.insert(-a);
    }

    ll cnt=0;
    while(se.size()){
      auto it = se.begin();

      ll a = -1 * (*it);
      se.erase(it);

      // aに対応する値は
      ll b = f(a);
      b *= -1;

      if(se.count(b)){
        auto it2 = se.find(b);
        se.erase(it2);
        cnt++;
      }
    }
    p(cnt);

    return 0;
}