AtCoder AGC 029 B - Powers of two (水色, 600 点)

「交換しても悪化しない」というのは Greedy の証明の共通構造だとは思う。

問題へのリンク

問題概要

個の正の整数 がある。
これらの 個の整数に対応する 頂点のグラフを考えて、和が の形で表せる 2 数間に辺を引く。

このグラフの最大マッチングを求めよ。

制約

• 
• 

考えたこと

2 の冪乗。。。これは構造があるにちがいない。

きっとなんか Greedy に解ける構造があって、それに従えば「交換しても悪化しない」的な感じになってるはず。

ルール付けとして、常に「2 数のうち大きい方から小さい方を選ぶ」という観点で考えてみる。

そうすると、例えば 51 とかとペアにりうるのは 13 しかない。一般に、a に対してペアになりうるのは a より大きい最小の 2 べきを 2^t として 2^t - a しかない。

だから結局は最大個数の「大きいやつ」を選んであげて、そのペアが取り合いにならないようにする問題になるのだけど、そう考えると

• 大きい方から見ていって、ペアが残っていたら後先考えずにマッチングさせてしまう

という Greedy でいいことが自然にわかる。というのも、その大きいやつを残しておくメリットはない。端から詰めて損することはない。

#include <iostream>
#include <vector>
#include <map>
using namespace std;

void dec(map<long long, long long> &ma, long long a) {
    ma[a]--;
    if (ma[a] == 0) {
        ma.erase(a);
    }
}

int main() {
    int N; cin >> N;
    vector<long long> a(N);
    for (int i = 0; i < N; ++i) cin >> a[i];
    map<long long, long long> ma;
    for (int i = 0; i < N; ++i) ma[-a[i]]++;

    long long res = 0;
    for (int i = 0; i < N && !ma.empty(); ++i) {
        long long val = -ma.begin()->first;
            
        dec(ma, -val);
        long long po = 1;
        while (po <= val) po *= 2;
        long long rem = po - val;
        if (ma.count(-rem)) {
            ++res;
            dec(ma, -rem);
        }
    }
    cout << res << endl;
}