Codeforces Round #213 (Div. 1) C. Beautiful Set

問題

codeforces.com

解法

適当に書いたら通ってしまったという感じ(解説を見ると writer もいろいろ解法ありそうと思っていたようです)なので証明も何もないんですが, やったことを書きます。

素数の limit 番目まで使う, と決めた時, どのような整数集合がいい感じかを考えます。
例えば, 2, 3, 5 を使うとした時, 2*3*5 = 30 に対して 2, 3, 5 をいくつか掛けたやつは, 必ず 2 でも 3 でも 5 でも割れるので有利です。次に考えたいのは, 3*5 = 15 に対して 3, 5 をいくつか掛けたやつ, 次は (2, 5) の組み合わせ, ... みたいな感じです(2*3*5 の組み合わせだけは間違いなく最初にやった方が良いですが, あとはなんとなくそのほうが良い, というだけでなんでこれで上手く行くのか説明は出来ません)。

こんな感じで, s = (2^limit)-1 から s = 1 まで順番に, 整数集合を増やしていくことにします。

できた集合が条件を満たしていればそれを出力したら AC 出来ました。

int prime[15] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47};

set<int> solve(int limit, int k) {
    set<int> ret;
    for (int s = (1<<limit)-1; s > 0; s--) {
        int p = 1;
        bool ng = false;
        for (int i = 0; i < 15; i++) {
            if ((s>>i)&1) {
                p *= prime[i];
                if (p > 2*k*k) {
                    ng = true;
                    break;
                }
            }
        }
        if (ng) continue;
        queue<int> que;
        que.push(p);
        while (!que.empty() && ret.size() < k) {
            int now = que.front(); que.pop();
            ret.insert(now);
            for (int i = 0; i < 15; i++) {
                if ((s>>i)&1) {
                    int next = now*prime[i];
                    if (next <= 2*k*k) que.push(next);
                }
            }
        }
        if (ret.size() == k) return ret;
    }
    return ret;
}

int cnt[15];

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int k;
    cin >> k;
    for (int i = 1; i < 15; i++) {
        set<int> S = solve(i, k);
        if (S.size() < k) continue;
        memset(cnt, 0, sizeof(cnt));
        for (int el : S) {
            for (int i = 0; i < 15; i++) if (el%prime[i] == 0) cnt[i]++;
        }
        bool ng = false;
        for (int i = 0; i < 15; i++) {
            if (cnt[i] != 0 && 2*cnt[i] < k) ng = true;
        }
        if (ng) continue;
        for (int el : S) {
            cout << el << " ";
        }
        cout << endl;
        break;
    }
    return 0;
}