京都大学プログラミングコンテスト2014 C - 占い

問題

kupc2014.contest.atcoder.jp

解法

i 回目の操作では A[i%N], B[i%M] が一致していないといけない, という要求がたくさん来ているので, 一致させれば良いわけですが, 例えば A[*], B[*] のすべての値が一致してしまうと, 相性度は 0 になってしまいます(これを考えると, 相性度はたかだか N*M であることがわかる)。

手順が終わらなくて相性度が 0 になる, というのを避けるためには, ある i が存在して, gcd(i, j) = gcd(N, M) を満たす j のいずれかについて A[i] != B[j] が成り立っていなければなりません。

相性度が t 以上になるかどうかを確かめる場合には, t 個目まで A[i%N] と B[i%M] の値を同じグループにするように unite して, その後 gcd(i, j) = gcd(N, M) を満たす i, j について A[i] と A[j] が別のグループになっているようなものがあれば相性度は t 以上, そうでなければ相性度は t 未満とわかります。これを使って二分探索をすれば良いです。

struct UnionFind {
    vector<int> par;
    int n, cnt;
    UnionFind(const int& x = 0) {init(x);}
    void init(const int& x) {par.assign(cnt=n=x, -1);}
    inline int find(const int& x) {return par[x] < 0 ? x : par[x] = find(par[x]);}
    inline bool same(const int& x, const int& y) {return find(x) == find(y);}
    inline bool unite(int x, int y) {
        if ((x = find(x)) == (y = find(y))) return false;
        --cnt;
        if (par[x] > par[y]) swap(x, y);
        par[x] += par[y];
        par[y] = x;
        return true;
    }
    inline int count() const {return cnt;}
    inline int count(int x) {return -par[find(x)];}
};

int N, M, Q;
int c[222], d[222];

bool check(int t) {
    UnionFind uf(N+M);
    for (int i = 0; i < Q; i++) {
        uf.unite(c[i], N+d[i]);
    }
    for (int i = 0; i < t; i++) {
        uf.unite(i%N, (i%M)+N);
    }
    int g = __gcd(N, M);
    for (int i = 0; i < N; i++) {
        int q = i%g;
        for (int j = q; j < M; j+= g) {
            if (!uf.same(i, j+N)) return true;
        }
    }
    return false;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> N >> M >> Q;
    for (int i = 0; i < Q; i++) {
        cin >> c[i] >> d[i];
        c[i]--; d[i]--;
    }
    int low = 0, high = N*M+1;
    while (high-low > 1) {
        const int med = (high+low)/2;
        if (check(med)) low = med;
        else high = med;
    }
    if (check(low)) cout << low+1 << endl;
    else cout << low << endl;
    return 0;
}