2014 Yandex.Algorithm Elimination Stage, Round 2 F - Permutation Cube

問題文

解法

X, Y, Z のそれぞれについて，巡回するいくつかのグループに分けることができる．
周期 a で巡回する列と，周期 b で巡回する列と，周期 c で巡回する列を考える．これらはそれぞれ X, Y, Z から持ってくるとする．
このとき，これらの全体としての周期は lcm(a, b, c) である．
これは何を意味するかと言うと，この3つの列のすべての数を網羅するためには，a * b * c / lcm(a, b, c) 回のコスト1の移動が必要であるということである．
したがって，X, Y, Z のそれぞれについて，巡回する部分のサイズをそれぞれ求めて，3重ループですべての3組の巡回列について計算すればよい．
当然これをそのままやるとオーダーがヤバイのだが，同じサイズの巡回列は map でまとめてしまうとオーダーが落ちる．
なぜなら，高々サイズの種類数は sqrt(N) 通りしか無いからである(1 + 2 + ... + N = N * (N + 1) / 2 であるため）．
よって，この3重ループは O(Nsqrt(N)) となり，間に合う．

ソースコード

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

using ll = long long;

ll lcm(ll a, ll b, ll c) {
    const ll t = a * b / __gcd(a, b);
    return t * c / __gcd(t, c);
}

class union_find {
public:
    union_find(int n) : par(n, -1) {}

    int root(int x) {
        return par[x] < 0 ? x : par[x] = root(par[x]);
    }

    void unite(int x, int y) {
        x = root(x), y = root(y);
        if(x == y) return;
        if(par[x] > par[y]) swap(x, y);
        par[x] += par[y];
        par[y] = x;
    }

    int size(int x) {
        return -par[root(x)];
    }

private:
    vector<int> par;
};

int main() {
    int n;
    cin >> n;
    vector<int> x(n), y(n), z(n);
    vector<union_find> uf(3, n);
    for(int i = 0; i < n; ++i) {
        cin >> x[i];
        uf[0].unite(i, x[i] - 1);
    }
    for(int i = 0; i < n; ++i) {
        cin >> y[i];
        uf[1].unite(i, y[i] - 1);
    }
    for(int i = 0; i < n; ++i) {
        cin >> z[i];
        uf[2].unite(i, z[i] - 1);
    }

    vector<vector<bool>> used(3, vector<bool>(n));
    vector<unordered_map<int, int>> cnt(3);
    for(int i = 0; i < 3; ++i) {
        for(int j = 0; j < n; ++j) {
            const int r = uf[i].root(j);
            if(used[i][r]) continue;
            used[i][r] = true;
            cnt[i][uf[i].size(r)] += 1;
        }
    }

    ll ans = 0;
    for(auto& p1 : cnt[0]) {
        for(auto& p2 : cnt[1]) {
            for(auto& p3 : cnt[2]) {
                const ll sz1 = p1.first, sz2 = p2.first, sz3 = p3.first;
                const ll cycle = lcm(sz1, sz2, sz3);
                ans += sz1 * sz2 * sz3 / cycle * p1.second * p2.second * p3.second;
            }
        }
    }

    cout << ans << endl;
}

感想

さすがに典型．油断してるとオーバーフローするのが罠なぐらいか．