motu*2

DIV1目指して問題を解き続ける

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;
    }
};