TopCoder SRM 640 DIV2 Level2
概要
始めx=1とする。各ステップで2xか、2x+1に値を変えることができ、
最大k-1回までできる。
禁止の値リストがあり、この値にすることはできない。
作れる数字の合計を答える。
解法
tableを昇順にソートする。
図のように深さkの二分木となっているため、table[i]を親とすると
子要素は2^(table[i]の深さ - 二分木の深さ) - 2個ある。
合計を2^二分木の深さとし、子要素の数 + 1 だけ引いていく。
i番目の要素の親要素(0 ~ i-1)が、すでに使われていれば、引かないようにする。
親要素であるかどうかは、2で割っていって確かめる。
コード
#include <iostream> #include <cstdio> #include <cstring> #include <vector> #include <climits> #include <algorithm> #include <cmath> #include <cstdlib> #include <stack> #include <queue> #include <string> #include <map> #include <set> #include <sstream> #include <functional> #include <ctime> using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair<int, int> PII; #define FOR(i,a,b) for(int i=(a);i<(b);i++) #define REP(i,n) FOR(i,0,n) #define CLEAR(d) memset((d), 0, (sizeof((d)))) #define ALL(c) (c).begin(), (c).end() #define ABS(x) ((x < 0) ? -(x) : (x)) #define SORT(x) sort((x).begin(), (x).end()) #define RSORT(x) sort((x).begin(), (x).end(), greater<int>() ) #define SIZE(a) ((int)((a).size())) #define MOD 1000000007 #define EPS 1e-7 #define PI (acos(-1)) #define INF 10000000 struct edge { int to; int cost; }; //=================================================== class NumberGameAgain { public : long long solve(int k, vector<long long> table) { long long sum = pow(2, k) - 2; sort(table.begin(), table.end()); for (int i = 0; i < table.size(); i++) { int flag = 0; for (long long n = table[i] / 2; n >= 2; n /= 2) { for (int j = 0; j < i; j++) { if (n == table[j]) { flag = 1; break; } } if (flag) break; } if (flag) continue; int l2 = log2(table[i]); sum -= pow(2, k - l2) - 1; } return sum; } };