TopCoder SRM 615 Div1 Easy AmebaDiv1 [1人競技プログラミング Advent Calendar 2016 15日目]

この記事は1人競技プログラミング Advent Calendar 2016 15日目の記事です。

問題概要：
TopCoder Statistics - Problem Statement
アメーバは自分と同じサイズのゲルのみを食べることが出来る。
N(1<=N<=200)匹のゲルのサイズの配列X(1<=X[i]<=1,000,000,000)が与えられる。
アメーバは0番目からN-1番目まで順番にゲルを食べれたら食べていく。

アメーバの初期サイズが任意に決められる際に存在しない最終的なアメーバのサイズは何通りあるかを答えよ。

解いた方法：
初期サイズがゲルのいずれかの値と一致しない場合は1度もアメーバはゲルを食べることが出来ないので、最終的なサイズはそのままになる。
ということは、調べる必要があるアメーバの初期サイズは1度以上ゲルを食べるサイズのみで良い。

そうすると高々初期サイズ200通りを調べるだけで良いので、全通り試して適当にsetにぶち込めば終わる。

#include<bits/stdc++.h>

#define MP make_pair
#define PB push_back
#define ALL(x) (x).begin(),(x).end()
#define REP(i,n) for(int i=0;i<(n);i++)
#define REP1(i,n) for(int i=1;i<(n);i++)
#define REP2(i,d,n) for(int i=(d);i<(n);i++)
#define RREP(i,n) for(int i=(n);i>=0;i--)
#define CLR(a)      memset((a),0,sizeof(a))
#define MCLR(a)     memset((a),-1,sizeof(a))
#define RANGE(x,y,maxX,maxY) (0 <= (x) && 0 <= (y) && (x) < (maxX) && (y) < (maxY))

using namespace std;

typedef long long LL;
typedef unsigned long long ULL;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef vector<LL> VLL;
typedef pair<int,int> PII;

const int INF = 0x3f3f3f3f;
const LL INFL = 0x3f3f3f3f3f3f3f3fLL;
const double EPS = 1e-9;

const int DX[]={1,0,-1,0},DY[]={0,-1,0,1};

class AmebaDiv1 {
    public:
    vector<int> X;
    int count(vector<int> _XX) {
        X = _XX;
        set<int> X_set;
        set<int> goal;

        REP(i, X.size()){
            X_set.insert(X[i]);
            int now = X[i];
            REP(j, X.size()){
                if(X[j] == now) now *= 2;
            }

            REP(j, X.size()){
                if(X[j] == now){
                    goal.insert(now);
                    break;
                }
            }
        }

        return X_set.size()-goal.size();
    }
};