SRM615 Div1 Easy "AmebaDiv1"

問題

TopCoder Statistics - Problem Statement

訳

モンテカルロはアメーバである。アメーバはゲルを餌にすることができる。アメーバが自分と大きさが同じゲルが与えられたとき、アメーバはゲルを取り込み、自身の大きさは２倍になる。

最初に、モンテカルロのサイズは正の整数であることしか分かっていない。生きている間、モンテカルロはゲルを複数回与えられ、それを取り込むこととなる。

あなたはint配列 X が与えられる。X[i]はモンテカルロに与えられるi番目のゲルのサイズである。

Sをモンテカルロの最終的なサイズの取りうる値のセットとする。Sに含まれない正の整数が何個あるかを返せ。

制約

1 <= Xのサイズ <= 200
1 <= X[i] <= 10^9

考えたこと

Sに入らない値はXにあるものだけなので、Xにあるやつを初期値としてシミュレートしていき最終のサイズを出す。シミュレートでだした最終のサイズとXでかぶってないやつの数が答え。

ソースコード

class AmebaDiv1 {

    public:

    int count(vector <int> X) {

        int n = X.size();
        vector<int> cand;

        for (int i = 0; i < n; i++) {
            bool ok = true;
            for (int j = i + 1; j < n; j++) {
                if (X[i] == X[j]) ok = false;
            }
            if (ok) cand.push_back(X[i]);
        }

        vector<int> rem;
        for (int i = 0; i < cand.size(); i++) {

            int size = cand[i];
            for (int j = 0; j < n; j++) {
                if (size == X[j]) size *= 2;
            }

            rem.push_back(size);
        }

        int res = 0;
        for (int i = 0; i < cand.size(); i++) {
            bool ok = true;
            for (int j = 0; j < rem.size(); j++) {
                if (cand[i] == rem[j]) ok = false;
            }
            if (ok) res++;
        }

        return res;
    }
};