はまやんはまやんはまやん

hamayanhamayan's blog

Permutation Cycle [ICM Technex 2018 and Codeforces Round #463 (Div. 1 + Div. 2, combined) C]

http://codeforces.com/contest/932/problem/C

f(i,j) := P[i] (j=1)
f(i,j) := f(P[i], j-1) (otherwise)
と定義される関数fがある。
関数g(i)をf(i,j)=iとなる最小のjと定義する。
g(1), g(2), ..., g(N)の値がAかBのいずれかになるように順列Pを構築せよ。
不可能なら"-1"

解法

http://codeforces.com/contest/932/submission/35302250

よくある順列をiからP[i]へ辺を貼るグラフを考える。
すると、g(i)は頂点iから遷移してiに到達する最低回数を返す。
そのため、グラフを作成していくときに、連結成分がそれぞれ頂点数AかBとなるように作ればいい。
構築出来るかは、N=A*a+B*bのように表現できるかによる。
まずは、aを全探索して、N=A*a+B*bを満たすa,bを探そう。
 
あとは、A頂点毎にサイクルをa個作り、B頂点毎にサイクルをb個作って答える。

int N, A, B, ans[1010101];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> A >> B;

    int aa = -1, bb = -1;

    rep(a, 0, N / A + 1) {
        int res = N - a * A;
        if (res % B == 0) {
            aa = a;
            bb = res / B;
            break;
        }
    }

    if (aa < 0) {
        printf("-1\n");
        return;
    }

    int idx = 0;
    rep(a, 0, aa) {
        rep(i, 0, A - 1) ans[idx + i + 1] = idx + i;
        ans[idx] = idx + A - 1;
        idx += A;
    }
    rep(b, 0, bb) {
        rep(i, 0, B - 1) ans[idx + i + 1] = idx + i;
        ans[idx] = idx + B - 1;
        idx += B;
    }

    rep(i, 0, N) {
        if (i) printf(" ");
        printf("%d", ans[i] + 1);
    }
    printf("\n");
}