Educational Codeforces Round 4 E. Square Root of Permutation
解法
順列では「順列 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 の2つ先が j, j の 2 つ先が i」となっています)。
- ループに含まれる頂点数が偶数の場合
- この場合は, 奇数の場合と違って, 単体ではどうしようもないので, 2 つの順列を組み合わせます。偶数の同じ長さで, 偶数個のループがなかったら, それは -1 を出力することになります。
- 例えば, i -> j -> i と k -> l -> k というグラフがあったら, i -> k -> j -> l -> i という感じです。交互に2つの順列の値を入れていくイメージですね。
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; }