Codeforces Round #184 (Div. 2) C. Ivan and Powers of Two
難しくない普通の問題。ちょっと好きかも。
C. Ivan and Powers of Two
問題
$n$個の非負整数$a_1, a_2, \dots, a_n$が与えられる。 ここにいくつかの非負整数$a_{n+1}, a_{n+2}, \dots, a_{n+k}$を加えて以下の条件を満たすようにしたい。
- ある整数$v$が存在し、$\Sigma 2^{a_i} = 2^v-1$
加える整数の数の最小値を答えよ。
解法
まず、2の羃を取る必要はない。 数列内に整数$n$が2つ含まれていればその2つを取り除き$n+1$を加える、という操作を可能な限り繰り返した結果、sortした数列が$0, 1, 2, \dots, v-1, v$という形をしていればよい。
数列をsortして下から見ていき、重複があれば繰り上げ、抜けている数があれば追加し、最終的にいくつ追加したかを答えればよい。
実装
#include <iostream>
#include <vector>
#include <set>
#include <functional>
#define repeat(i,n) for (int i = 0; (i) < (n); ++(i))
typedef long long ll;
using namespace std;
int main() {
int n; cin >> n;
vector<ll> a(n); repeat (i,n) cin >> a[i];
set<ll> b;
function<void (ll)> push; push = [&](ll it) {
if (b.count(it)) { // carry
b.erase(it);
push(it + 1);
} else {
b.insert(it);
}
};
for (ll it : a) push(it);
ll result = 0;
ll last = -1;
for (ll it : b) {
result += it - last - 1;
last = it;
}
cout << result << endl;
return 0;
}