けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AtCoder ARC 110 F - Esoswap (橙色, 900 点)

AtCoder AtCoder900点 橙色diff ARC-F 順列を題材とした問題 順列テク:巡回群の直積と見る 操作 ソートすることが目的の操作の問題 操作:swap 構築 Yes/No判定問題

コンテスト後に AC して、解けた気持ちになっていたけど、その解法は嘘だった

問題概要

0, 1, \dots, N-1 の順列 P_{0}, P_{1}, \dots, P_{N-1} が与えられる。以下の操作を最大 200000 回まで繰り返すことでソートされた状態にせよ。

  • i = 0, 1, \dots, N-1 のいずれかを選んで
  • P_{i} と P_{(i + P_{i}) \mod N} を swap する

不可能である場合は -1 を出力せよ。

制約

  • 1 \le N \le 100

考えたこと：嘘解法

まず、仮に P を対称群と見たときに全体が位数 N の巡回群になっているならば、実は i = 0 を連打するだけでソートすることができることがわかった。なぜならその操作は、

  • v = P_{0} としたとき
  • P_{v} = v を成り立たせた上で、残りの要素を新たな巡回群とする

というものになるからだ。よって問題は、与えられた順列をいくつかの巡回群の直積に分解したとき、適切に swap を繰り返すことで巡回群をマージしていき、最終的に 1 つの巡回群が形成されるようにすることだと考えた。

そして 2 つの巡回群 C_{1}, C_{2} があったとき、もし C_{1} のある要素 v が存在して、 v + P_{v} が C_{2} の要素であったならば、 v に対する操作によって C_{1}, C_{2} が合体して 1 つの巡回群になることもわかった。

この時点では、「ある巡回群とその要素が存在して、その行先が他の巡回群に属する」という性質が成り立つか確証がなかった (反例があった) けど、成り立つものだとして実装したら通った。

Submission #18602400 - AtCoder Regular Contest 110（Sponsored by KAJIMA CORPORATION）

反例として P = (0, 3, 1, 4, 2) がある (ぽかいこさんより)。実際上は、上位の性質が成り立たなかったとしても、適当にかき混ぜることで上記の性質が成り立つ状態にできそうではある。また、乱択が通ったという報告もある。

一応上記の反例対策として、上記の性質が成り立たないときは P_{j} = 1 を満たす j を叩くという処理を入れれば、反例をすり抜けた。これでもまだ反例があるかはわからない。

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

bool check(int N, vector<int> P) {
    for (int i = 0; i < N; ++i) if (P[i] != i) return false;
    return true;
}

vector<vector<int>> divide(int N, vector<int> P) {
    vector<bool> seen(N, false);
    vector<vector<int>> comp;
    for (int i = 0; i < N; ++i) {
        if (seen[i]) continue;
        vector<int> tmp({i});
        seen[i] = true;
        int j = P[i];
        while (j != i) {
            tmp.push_back(j);
            seen[j] = true;
            j = P[j];
        }
        comp.push_back(tmp);
    }
    return comp;
}

void solve(int N, vector<int> P, vector<int> &res) {
    while (true) {
        auto comp = divide(N, P);
        int i = 0, j = -1;
        for (i = 0; i < N; ++i) {
            if (P[i] == 1) j = i;
            vector<int> P2 = P;
            swap(P2[i], P2[(i+P2[i])%N]);
            auto comp2 = divide(N, P2);
            if (comp2.size() < comp.size()) {
                res.push_back(i);
                swap(P[i], P[(i+P[i])%N]);
                break;
            }
        }
        if (comp.size() == 1) break;
        if (i == N) {
            res.push_back(j);
            swap(P[j], P[(j+P[j])%N]);
        }
    }
    while (!check(N, P)) {
        res.push_back(0);
        swap(P[0], P[P[0]]);
    }
}

int main() {
    int N; cin >> N;
    vector<int> P(N);
    for (int i = 0; i < N; ++i) cin >> P[i];
    vector<int> res;
    solve(N, P, res);
    cout << res.size() << endl;
    for (auto v : res) cout << v << endl;
}

想定解法

editorial が天才だった。

atcoder.jp

maspy さんの方法

面白かった

付記

print(-1)

を出力すると、すべて構築可能かどうかがわかるというテクニックがあるみたい。たしかに！！