Educational Codeforces Round 4 E. Square Root of Permutation

問題

codeforces.com

解法

順列では「順列 p の i 番目の値が p[i] だったら i -> p[i] に有向辺を貼ってグラフを作る」というのがよくあります。

この考えで問題文の順列 q のグラフを作り, そこから p = q^2 を作ることを考えると, p[i] は, 「q のグラフで i から 2 つ先の頂点」になります。例えばサンプルの 3 つ目では 4 5 1 2 3 というのがもとの q らしいですが, これは 1 -> 4 -> 2 -> 5 -> 3 -> 1 というループになっています。

なので, p をここから再構成すると,

• 1 -> 4 -> 2 より p[1] = 2
• 2 -> 5 -> 3 より p[2] = 3
• 以下略

みたいな感じで, 確かに q から p が構成できていることがわかります。

では p のグラフが与えられた時 q を構成することを考えます。

順列のグラフで特徴的なことは, 「すべての頂点 v がそこから出る辺(v -> u)を一つ持ち, かつそこへ向かう辺(u -> v) を一つ持つ」ということです。この性質から, グラフはいくつかのループから構成されることになります。さっきの例では全体でひとつのループになりましたが, 1 つ目の例とかだといくつかのループになっていたと思います。

で, 各ループに含まれる頂点の数の偶奇で場合分けします。

• ループに含まれる頂点数が奇数の場合
  • この場合は, 順列 p について i -> j という辺が引かれているなら, i -> (なんか頂点) -> j という形に必ずできるので, そのようにグラフを構成していきます(例えば順列 p で i -> k -> j というループだったら, i -> j -> k -> i というようにすれば, 「i の 2 つ先が j, k の２つ先が j, j の 2 つ先が i」となっています)。
• ループに含まれる頂点数が偶数の場合
  • この場合は, 奇数の場合と違って, 単体ではどうしようもないので, 2 つの順列を組み合わせます。偶数の同じ長さで, 偶数個のループがなかったら, それは -1 を出力することになります。
  • 例えば, i -> j -> i と k -> l -> k というグラフがあったら, i -> k -> j -> l -> i という感じです。交互に２つの順列の値を入れていくイメージですね。

const int MAXN = 1000100;
int p[MAXN], ans[MAXN];
bool done[MAXN];
vector<vi> G[MAXN];

int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        scanf("%d", p+i);
        p[i]--;
    }
    for (int i = 0; i < n; i++) {
        if (done[i]) continue;
        vector<int> v;
        int cur = i;
        while (1) {
            if (done[cur]) break;
            done[cur] = true;
            v.push_back(cur);
            cur = p[cur];
        }
        G[v.size()].push_back(v);
    }
    for (int i = 1; i <= n; i++) {
        if (i%2) {
            for (const vi& v : G[i]) {
                for (int j = 0; j < i; j++) {
                    int next = ((i+1)/2 + j) % i;
                    ans[v[j]] = v[next];
                }
            }
        } else {
            int size = G[i].size();
            if (size%2) {
                cout << -1 << endl;
                return 0;
            }
            for (int j = 0; j < size; j+=2) {
                const vector<int>& v = G[i][j];
                const vector<int>& u = G[i][j+1];
                for (int k = 0; k < i; k++) {
                    ans[v[k]] = u[k];
                    ans[u[k]] = v[(k+1)%i];
                }
            }
        }
    }
    for (int i = 0; i < n; i++) {
        printf("%d ", ans[i]+1);
    }
    printf("\n");
    return 0;
}