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

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

AtCoder ARC 110 C - Exoswap (緑色, 500 点)

「転倒数 = N-1 で Yes とする」という嘘解法が大量に通ったらしい

問題概要

 1, 2, \dots, N の順列  P_{1}, P_{2}, \dots, P_{N} が与えられる。

  •  P_{1} P_{2} を swap する
  •  P_{2} P_{3} を swap する
  • ...
  •  P_{N-1} P_{N} を swap する

という  N-1 種類の操作を、それぞれちょうど 1 回ずつ行う必要がある。その結果がソートされた状態にすることが可能かどうか判定し、可能ならば具体的な手順を提示せよ。

制約

  •  2 \le N \le 2 \times 10^{5}

考えたこと

この手の問題は、最大値や最小値に着目するといいことがあったりする。ひとつ言えるのは、1 は最終的に左端に来なければならないので、仮に

  •  P_{i-1} \neq 1
  •  P_{i} = 1

となる箇所があったならば、 j = 1, 2, \dots, i-1 に対するどの操作よりも、 j = i に対する操作を行う必要がある。同様に考えて

「操作  i, i-1, \dots, 1 をこの順に行うとしてしまってよい」

ということが言える。このとき、 P_{0}, \dots, P_{i-1} については二度と値を変更できないので、これらが  P_{i} = i を満たさない場合は false となる。

これらを実施した結果、今度は  P_{i}, P_{i+1}, \dots, P_{N-1} に対して再帰的に同様に処理していけば OK。このとき、

  •  P_{i}, P_{i+1}, \dots, P_{N-1} の最小値
  • 最小となる index

を高速に求めたい。コンテスト中は RMQ を使って通した。しかしながら最小値が  i であることはわかっているので、  P逆行列  P' を予め計算しておけば、P'[i] を参照するだけでよかった。

コード

計算量は  O(N) となる。

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

int N;
vector<int> P, iP;

bool solve(int left, vector<int> &res) {
    if (res.size() == N-1) {
        for (int i = 0; i < N; ++i) if (P[i] != i) return false;
        return true;
    }
    if (iP[left] <= left) return false;
    for (int j = iP[left]; j > left; --j) {
        res.push_back(j);
        swap(P[j], P[j-1]);
    }
    for (int j = left; j < iP[left]; ++j) if (P[j] != j) return false;
    return solve(iP[left], res);
}

int main() {
    cin >> N;
    P.resize(N), iP.resize(N);
    for (int i = 0; i < N; ++i) cin >> P[i], --P[i], iP[P[i]] = i;
    vector<int> res;
    if (!solve(0, res)) cout << -1 << endl;
    else for (auto v : res) cout << v << endl;
}