Quiz
https://atcoder.jp/contests/agc029/tasks/agc029_b
AC code
https://atcoder.jp/contests/agc029/submissions/13113984
解説
- 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; }