2020-12-12

AOJ 3215 Construction Set (OUPC 2020 G)

AOJ OUPC 有志コンマッチング二部グラフフローグラフ最大安定集合・最小点被覆・最小辺被覆数学(整数問題) Greedy Greedy:後によいものを残す・今が良いほど未来も良い復元約数どれか1つ求める互いに素素因数分解パリティ倍数判定や九去法【問題集】フローのステップアップ

二部マッチングの復元にてこずって、間に合わなかった...

問題概要

$N$ 個の正の整数 $A_{1}, \dots, A_{N}$ の部分集合であって、以下の条件を満たすもののうち、要素数が最大のものを 1 つ求めよ。

どの要素も 6 で割ったあまりが 1 ではない
どの要素も約数の個数がちょうど 4 個である
どの要素も 6 で割ったあまりが互いに等しい
どの 2 つの要素も互いに素である

制約

$1 \le N \le 5000$
$1 \le A_{i} \le 10^{9}$

考えたこと

見た目がとても面白そうだったので、ICPC ルールじゃなかったら真っ先にこれに突っ込んでたかもしれない！！

まず、6 で割ったあまりがすべて等しいと言っているので、0, 2, 3, 4, 5 の場合をそれぞれ考えたくなるのだけど、

6 で割って 0 あまるやつは全員 6 の倍数
6 で割って 2 あまるやつは全員 2 の倍数
6 で割って 3 あまるやつは全員 3 の倍数
6 で割って 4 あまるやつは全員 2 の倍数

となっているので、それぞれ最大でも 1 個だけとなる。6 で割って 5 あまる整数が存在しない場合に限り、これらの選択肢も検討すれば OK。

以後、6 で割って 5 あまる整数のみを抽出して考えることにする。それらの約数の個数が 4 個であるパターンは次の 2 つのみである。

$q$ を 6 で割って 5 あまる素数として、 $q^{3}$ と表せる整数
$p$ を 6 で割って 1 あまる素数, $q$ を 6 で割って 5 あまる素数として、 $pq$ と表せる整数

よって、前者を無視すれば、「6 で割って 1 あまる素数」と「6 で割って 5 あまる素数」との間の二部マッチングになりそうだ。「どの 2 つの要素も互いに素である」という条件が、「マッチングをなすペアが、同じ素数を共有しない」という条件にピッタリ対応する。

最後に、 $q^{3}$ というパターンについてだが、これは予めすべて採用してしまって問題ない。なぜなら、

仮に $q$ を含むマッチングが存在しない場合には、単純に $q^{3}$ を追加することで個数を 1 個増やせる
$q$ を含むマッチング $(p, q)$ が存在していたとしても、それを削除して代わりに $q^{3}$ を追加しても条件を満たしている

というふうになっているからだ。いずれにしても、 $q^{3}$ の形をしたものはかならず選ぶものとしてよい。そして、それ以外の素数について二部マッチングをすれば OK。

計算量は、Hopcroft-Karp 法を用いた場合、 $O(N\sqrt{N} + N\sqrt{A})$ となる。

コード

#include <bits/stdc++.h>
using namespace std;

struct HopcroftKarp {
    int sizeL, sizeR;
    vector<vector<int> > list; // left to right
    
    // result
    vector<bool> seen, matched;
    vector<int> level, matching;
    
    // base
    HopcroftKarp(int l, int r) : sizeL(l), sizeR(r), list(l, vector<int>()) { }
    inline vector<int>& operator [] (int i) { return list[i]; }
    inline void addedge(int from, int to) { list[from].push_back(to); }
    inline friend ostream& operator << (ostream& s, const HopcroftKarp& G) {
        s << endl;
        for (int i = 0; i < G.list.size(); ++i) {
            s << i << " : ";
            for (int j = 0; j < G.list[i].size(); ++j) {
                s << G.list[i][j];
                if (j + 1 != G.list[i].size()) s << ", ";
            }
            s << endl;
        }
        return s;
    }
    
    // methods
    void hobfs() {
        queue<int> que;
        for (int left = 0; left < sizeL; ++left) {
            level[left] = -1;
            if (!matched[left]) {
                que.push(left);
                level[left] = 0;
            }
        }
        level[sizeL] = sizeL;
        while (!que.empty()) {
            int left = que.front();
            que.pop();
            for (int i = 0; i < list[left].size(); ++i) {
                int right = list[left][i];
                int next = matching[right];
                if (level[next] == -1) {
                    level[next] = level[left] + 1;
                    que.push(next);
                }
            }
        }
    }
    bool hodfs(int left) {
        if (left == sizeL) return true;
        if (seen[left]) return false;
        seen[left] = true;
        for (int i = 0; i < list[left].size(); ++i) {
            int right = list[left][i];
            int next = matching[right];
            if (level[next] > level[left] && hodfs(next)) {
                matching[right] = left;
                return true;
            }
        }
        return false;
    }
    int solve() {
        seen.assign(sizeL, false);
        matched.assign(sizeL, false);
        level.assign(sizeL+1, -1);
        matching.assign(sizeR, sizeL);
        int res = 0;
        while (true) {
            hobfs();
            seen.assign(sizeL, false);
            bool finished = true;
            for (int left = 0; left < sizeL; ++left) {
                if (!matched[left] && hodfs(left)) {
                    matched[left] = true;
                    ++res;
                    finished = false;
                }
            }
            if (finished) break;
        }
        return res;
    }
};

vector<long long> calc_divisor(long long n) {
    vector<long long> res;
    for (long long i = 1LL; i*i <= n; ++i) {
        if (n % i == 0) {
            res.push_back(i);
            long long j = n / i;
            if (j != i) res.push_back(j);
        }
    }
    sort(res.begin(), res.end());
    return res;
}

int main() {
    int N;
    cin >> N;
    vector<long long> A(N);
    for (int i = 0; i < N; ++i) cin >> A[i];

    auto solve = [&]() -> vector<long long> {
        vector<long long> okay, only;
        vector<long long> left, right; // (1, 5)
        set<long long> use;
        for (int i = 0; i < N; ++i) {
            auto div = calc_divisor(A[i]);
            if (A[i] % 6 == 1 || div.size() != 4) continue;
            if (A[i] % 6 == 5) {
                long long p = div[1], q = div[2];
                if (q % p == 0) use.insert(p);
                else {
                    if (p % 6 == 5) swap(p, q);
                    left.push_back(p), right.push_back(q); 
                }
                okay.push_back(A[i]);
            }
            else only.push_back(A[i]);
        }
        if (okay.empty()) {
            if (only.empty()) return vector<long long>();
            else return vector<long long>({only[0]});
        }
        sort(left.begin(), left.end());
        left.erase(unique(left.begin(), left.end()), left.end());
        sort(right.begin(), right.end());
        right.erase(unique(right.begin(), right.end()), right.end());

        int L = left.size(), R = right.size();
        HopcroftKarp G(L, R);
        for (auto a : okay) {
            auto div = calc_divisor(a);
            long long p = div[1], q = div[2];
            if (q % p == 0 || use.count(p) || use.count(q)) continue;
            if (p % 6 == 5) swap(p, q);
            int l = lower_bound(left.begin(), left.end(), p) - left.begin();
            int r = lower_bound(right.begin(), right.end(), q) - right.begin();
            G.addedge(l, r);   
        }
        int flow = G.solve();
        
        vector<long long> res;
        for (auto it : use) res.push_back(it * it * it);
        for (int r = 0; r < right.size(); ++r) {
            int l = G.matching[r];
            if (l >= L) continue;
            res.push_back(left[l] * right[r]);
        }
        return res;
    };
    
    auto res = solve();
    cout << (!res.empty() ? (long long)(res.size()) : -1) << endl;
    if (!res.empty()) {
        for (int i = 0; i < res.size(); ++i) cout << res[i] << " ";
        cout << endl;
    }
}

けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AOJ 3215 Construction Set (OUPC 2020 G)

問題概要

制約

考えたこと

コード