WARush

SRMの結果とか、解けた問題のコードを書いていきます

Codeforces #168 Div2 C "k-Multiple Free Set"

問題

k-Multiple Free Setとは、
任意の2つの要素x,y(x<y)において、x*k=yとなるような
要素のペアがない整数の集合である。

n個の整数の集合とkが与えられるので、
ここからk-Multiple Free Setとなるような部分集合を作った時の
最大の要素数を返せ。

制約

1 <= n <= 10^5
1 <= k <= 10^9
1 <= 与えられる整数の集合の値 <= 10^9

考えた事

例えば集合が2,3,4,5,6,7,8,9,10,11,12,13,14,15,16でk=2だとすると
2-4-8-16
3-6-12
5-10
7-14
9
11
13
ってグループになって
例えば2-4-8-16では、最大でも使えるのは2つ
3-6-12では6だけ使って3,12を使えなくするのはまずい

貪欲に小さい数から使ってけば問題なさそう

ソース
int N, K;

int main() {

    cin >> N >> K;

    set<int> s;       // 小さい順のセット
    map<int,bool> m; // その数字使える?
    for( int i = 0; i < N; i++ ){
        int t;
        cin >> t;
        s.insert(t);
        m[t] = true;
    }

    int res = 0;
    const int MAX_N = 1000000000;
    int max_d = MAX_N / K;
    for(set<int>::iterator it = s.begin(); it != s.end(); it++ ){
        int n = *it;
        if( m[n] ){
            res++;
            // n*Kは使えなくする
            // オーバーフローしないようにif付けといた
            if( max_d >= n ) m[n*K] = false;
        }
    }
    cout << res << endl;
}