2023-08-06

AtCoder ABC 210 F - Coprime Solitaire (橙色, 600 点)

2-SAT の「密」を解消する累積 OR テクを学んだ！

問題へのリンク

問題概要

$N$ 枚のカードがあり、表には $A_{i}$ 、裏には $B_{i}$ が書かれている。各カードについて、表を上にするか、裏を上にするかを選択していく。

上手く選択することで、上を向いている数値がどの 2 つも互いに素であるようにすることが可能かどうかを判定せよ。

制約

$1 \le N \le 3 \times 10^{4}$
$1 \le A_{i}, B_{i} \le 2 \times 10^{6}$

考えたこと

いかにも 2-SAT な問題だった。 $2N$ 個の整数を素因数分解して登場しうる各素数 $p$ に対して、次のように考えられる。

$A_{i}$ も $B_{i}$ も $p$ で割り切れるような $i$ の個数が 2 個以上ならば、直ちに "No"
その個数が 1 個ならば、そのような以外の各に対して、
- $A_{j}$ が $p$ の倍数ならば、 $B_{i}$ の方を選択しなければならない
- $B_{j}$ が $p$ の倍数ならば、 $A_{i}$ の方を選択しなければならない
その個数が 0 個ならば、それら $p$ で割り切れる $A_{i}$ や $B_{i}$ のうち、どの 2 つも同時に選択されてはならない

この最後の場合を掘り下げよう。 $A_{i}$ または $B_{i}$ が $p$ で割り切れるような $i$ を $i_{0}, i_{1}, \dots, i_{K-1}$ とする。

これら $K$ 個のうち、「どの 2 つも $p$ の倍数の側を選んではいけない」という制約は、2-SAT において、 ${}_{K}\mathrm{C}_{2}$ 個の節として表現できる。

このままでは計算量が厳しいので、次記事のテクニックを用いる。

drken1215.hatenablog.com

このテクニックを用いると、結局、 $2N$ 個の整数を素因数分解して登場する素因数の延べ個数を $A$ としたとき、 $O(A)$ の計算量で解けることとなる。

$M = \max_{i=1}^{N} \max(A_{i}, B_{i})$ として、 $A = O(N \log M)$ であるから、結局全体の計算量は $O(N \log M)$ となる。

コード

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


// Decomposition of Strongly Connected Component
struct SCC {
    using Edge = int;
    using Graph = vector<vector<Edge>>;

    // input
    Graph G, rG;

    // result
    vector<vector<int>> scc;
    vector<int> cmp;
    Graph dag;

    // constructor
    SCC(int N = 0) : G(N), rG(N) {}

    // various methods
    void add_edge(int u, int v) {
        G[u].push_back(v);
        rG[v].push_back(u);
    }

    // decomp
    vector<bool> seen;
    vector<int> vs, rvs;
    void dfs(int v) {
        seen[v] = true;
        for (auto e : G[v]) if (!seen[e]) dfs(e);
        vs.push_back(v);
    }
    void rdfs(int v, int k) {
        seen[v] = true;
        cmp[v] = k;
        for (auto e : rG[v]) if (!seen[e]) rdfs(e, k);
        rvs.push_back(v);
    }

    // reconstruct
    set<pair<int,int>> newEdges;
    void reconstruct() {
        dag.assign(scc.size(), vector<Edge>());
        newEdges.clear();
        for (int i = 0; i < (int)G.size(); ++i) {
            int u = cmp[i];
            for (auto e : G[i]) {
                int v = cmp[e];
                if (u == v) continue;
                if (!newEdges.count({u, v})) {
                    dag[u].push_back(v);
                    newEdges.insert({u, v});
                }
            }
        }
    }

    // main solver
    vector<vector<int>> find_scc(bool to_reconstruct = false) {
        // first dfs
        seen.assign((int)G.size(), false);
        vs.clear();
        for (int v = 0; v < (int)G.size(); ++v) if (!seen[v]) dfs(v);

        // back dfs
        int k = 0;
        scc.clear();
        cmp.assign(G.size(), -1);
        seen.assign(G.size(), false);
        for (int i = (int)G.size()-1; i >= 0; --i) {
            if (!seen[vs[i]]) {
                rvs.clear();
                rdfs(vs[i], k++);
                scc.push_back(rvs);
            }
        }

        // reconstruct DAG
        if (to_reconstruct) reconstruct();
        return scc;
    }
};

// 2-SAT Solver
struct TwoSATSolver : SCC {
    // input
    int num_variables;
    
    // result
    vector<int> solution;
    
    // constructor
    TwoSATSolver(int N = 0) : SCC(N * 2), num_variables(N), solution(N) {}
    
    // not
    inline int take_not(int x) {
        if (x < num_variables) return x + num_variables;
        else return x - num_variables;
    }
    
    // add closure
    void add_constraint(bool is_x_true, int x, bool is_y_true, int y) {
        assert(x >= 0 && x < num_variables);
        assert(y >= 0 && y < num_variables);
        if (!is_x_true) x = take_not(x);
        if (!is_y_true) y = take_not(y);
        add_edge(take_not(x), y);
        add_edge(take_not(y), x);
    }
    
    // main solver (if no solution, return empty)
    vector<int> solve() {
        find_scc();
        for (int i = 0; i < num_variables; ++i) {
            if (cmp[i] == cmp[take_not(i)]) return vector<int>();
            solution[i] = (cmp[i] > cmp[take_not(i)]);
        }
        return solution;
    }
};

void ABC_201_F() {
    // 素因数分解
    map<int, set<pair<bool, int>>> primes;
    auto extract_primes = [&](int m, bool which, int id) -> void {
        for (int p = 2; p*p <= m; ++p) if (m % p == 0) {
            primes[p].insert({which, id});
            while (m % p == 0) m /= p;
        }
        if (m > 1) primes[m].insert({which, id});
    };
    
    // 入力 (A: 0, B: 1)
    int N;
    cin >> N;
    vector<int> A(N), B(N);
    for (int i = 0; i < N; ++i) {
        cin >> A[i] >> B[i];
        extract_primes(A[i], false, i);
        extract_primes(B[i], true, i);
    }
    
    // 登録すべきリテラルをメモ
    struct closure {
        bool is1, is2;
        int lit1, lit2;
        closure(bool is1, int lit1, bool is2, int lit2)
        : is1(is1), lit1(lit1), is2(is2), lit2(lit2) {}
    };
    vector<closure> lits;
    int num = N;
    for (auto [p, ids] : primes) {
        int num_closures_both = 0;
        for (auto [which, id] : ids) {
            if (which && ids.count({!which, id})) ++num_closures_both;
        }
        
        if (num_closures_both  >= 2) {
            cout << "No" << endl;
            return;
        } else if (num_closures_both == 1) {
            // A[i] も B[i] も p で割り切れるなら、他は p で割れてはいけない
            for (auto [which, id] : ids) {
                if (ids.count({!which, id})) continue;
                lits.push_back(closure(!which, id, !which, id));
            }
        } else {
            int yiter = 0;
            for (auto [which, id] : ids) {
                lits.push_back(closure(!which, id, true, yiter+num));
                if (yiter) {
                    lits.push_back(closure(false, yiter-1+num, true, yiter+num));
                    lits.push_back(closure(false, yiter-1+num, !which, id));
                }
                ++yiter;
            }
            num += yiter;
        }
    }
    
    // 2-SAT を構築
    TwoSATSolver twosat(num);
    for (const auto &cl : lits)
        twosat.add_constraint(cl.is1, cl.lit1, cl.is2, cl.lit2);
    
    // 2-SAT を解く
    const auto &res = twosat.solve();
    cout << (!res.empty() ? "Yes" : "No") << endl;
    
    /*
    if(!res.empty()) {
        for (int i = 0; i < N; ++i) {
            if (twosat.solution[i]) cout << B[i] << " ";
            else cout << A[i] << " ";
        }
    }
    cout << endl;
     */
}


int main() {
    ABC_201_F();
}

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

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

AtCoder ABC 210 F - Coprime Solitaire (橙色, 600 点)

問題概要

制約

考えたこと

コード