ACM-ICPC Japan Alumni Group Summer Camp 2019 Day 1 - D Permutation Sort

問題

問題概要

長さの順列が与えられます。
1回の操作で、 に変換する、という操作を全てのについて行います。
全てのがとなるまでの操作回数の最小値を求めてください。

解法

何回か操作をするといずれループすることがわかります。
操作して初めてとなるような操作回数を、初期のに戻ってくるまでの操作回数(ループの長さ)をとすると、
を満たす最小のが答えになります。
解が存在しなかったり、が求まらなければ、答えは-1です。 これは中国剰余定理そのもので、拡張ユークリッドの互除法等で求めることができます(参考)。

感想

この分野は少し苦手なので今まで避けてきましたが、ようやく勉強することができました…一回書いておけば実装がそこまで重くないタイプに見えます。

提出コード

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

// as + bt = GCD(a,b) a,b:const s,t:var(any)
// return GCD(a,b)
long long extGCD(long long a, long long b, long long& s,
                 long long& t) {
    s = 1, t = 0;
    while(b) {
        long long tmp = a / b;
        a -= b * tmp;
        s -= t * tmp;
        swap(a, b);
        swap(s, t);
    }
    return a;
}

// x≡b_i(mod m_i) calc min x,lcm(m_i).
// if not exist, return (-1,-1)
pair<long long, long long> ChineseRem(
        const vector<long long>& b,
        const vector<long long>& m) {
    long long r = 0, lcm = 1;
    assert(b.size() == m.size());
    long long bsize = b.size();
    for(int i = 0; i < bsize; ++i) {
        long long p, q, d, now;
        d = extGCD(lcm, m[i], p, q);
        if((b[i] - r) % d != 0) return make_pair(-1, -1);
        now = (b[i] - r) / d * p % (m[i] / d);
        r += lcm * now;
        lcm *= m[i] / d;
    }
    return make_pair((r + lcm) % lcm, lcm);
}

long long n;
vector<long long> p,q,fmemo,lmemo;

long long solve();

int main(){
    cin >> n;
    p.resize(n);
    q.resize(n);
    fmemo.assign(n,0);
    lmemo.assign(n,0);
    for(int i = 0;i < n;++i){
        cin >> p[i];
        --p[i];
    }
    for(int i = 0;i < n;++i){
        cin >> q[i];
        --q[i];
    }
    cout << solve() << endl;
    return 0;
}

long long solve(){
    // prepair
    for(int i = 0;i < n;++i){
        long long now = p[i];
        bool ch = 0;
        for(int j = 0;j < n;++j){
            if(now == i){
                fmemo[i] = j;
                ch = 1;
            }
            now = q[now];
            if(now == p[i]){
                lmemo[i] = j + 1;
                break;
            }
        }
        if(!ch)return -1;
    }
    long long ans = 0;
    return ChineseRem(fmemo,lmemo).first;
}