「転倒数 = 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;
}

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

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

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

問題概要

制約

考えたこと

コード