AtCoder Grand Contest 029: B - Powers of two
解法
概要
\(A_i + A_j = 2^k\) であるような \((i, j)\) に辺を張ると答えはその最大マッチングの大きさとなる。 このグラフは木であることを信じれば \(O(N \log N)\) ぐらいで解ける。
詳細
自己ループと多重辺を無視したときにグラフ \(G\) が木であることを証明しておく。 数列の最大値 \(b = \max_i A_i\) の大きさで帰納法。 \(b = 1\) のときは明らか。 \(b \ge 2\) 未満での成立を仮定する。 グラフから \(b\) を除いた部分は木であるので \(b\) の次数が \(1\) であることを言えばよい。 \(b\) と辺が張られる数を考えると \(a \lt b\) かつ \(a + b = 2^k\) を満たす。 これを整理すると \(b \le 2^k \lt 2b\) となるので \(a\) は一意に定まる。 よってグラフ \(G\) は木である。
メモ
- \(2^k\) の \(k\) の上限が足りずに1WAした
- コンテスト中は雰囲気で通した
- 木であることの証明は解説放送を見た
実装
#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; (i) < (int)(n); ++ (i))
using namespace std;
int solve(int n, vector<int> const & a) {
unordered_map<int, int> f;
for (int a_i : a) {
f[a_i] += 1;
}
// construct the graph
unordered_map<int, vector<int> > g;
unordered_map<int, int> degree;
queue<int> que;
for (int a_i : a) if (not g.count(a_i)) {
REP (k, 31) {
int a_j = (1 << k) - a_i;
if (f.count(a_j)) {
g[a_i].push_back(a_j);
}
}
degree[a_i] = g[a_i].size();
if (degree[a_i] == 1) {
que.push(a_i);
}
}
// find the matching
int ans = 0;
while (not que.empty()) {
int a_i = que.front();
que.pop();
for (int a_j : g[a_i]) {
int delta = min(f[a_i], f[a_j]);
if (a_i == a_j) {
delta /= 2;
} else {
f[a_i] -= delta;
}
f[a_j] -= delta;
ans += delta;
}
for (int a_j : g[a_i]) {
degree[a_j] -= 1;
if (degree[a_j] == 1) {
que.push(a_j);
}
}
}
return ans;
}
int main() {
int n; cin >> n;
vector<int> a(n);
REP (i, n) cin >> a[i];
cout << solve(n, a) << endl;
return 0;
}