概要

現在の順列 \(p\) に対して、連続区間をちょうど \(1\) 回反転することで、目標の順列 \(q\) に一致させられるかを判定します。

考察

反転操作では、選んだ区間の外側の要素は一切変化しません。

そのため、もし \(p\) と \(q\) が異なる位置があるなら、その位置は必ず反転する区間に含まれている必要があります。

そこで、次のように考えます。

• 左から見て最初に \(p_i \neq q_i\) となる位置を \(L\)
• 右から見て最初に \(p_i \neq q_i\) となる位置を \(R\)

とします。

このとき、反転すべき区間は基本的に \([L, R]\) です。

例えば、

\(p = [1, 2, 3, 4, 5]\)

\(q = [1, 4, 3, 2, 5]\)

の場合、異なるのは位置 \(2\) から \(4\) までです。

\(p\) のその区間 \([2, 3, 4]\) を反転すると \([4, 3, 2]\) になり、\(q\) と一致します。

一方で、すべての \(L, R\) を試す方法では、区間の候補が \(O(N^2)\) 個あります。
\(N \leq 10^6\) なので、この方法では間に合いません。

重要なのは、反転区間の外側は変化しないため、最初と最後の不一致位置だけを見れば十分だということです。

また、もし最初から \(p = q\) なら、\(L = R\) のような長さ \(1\) の区間を反転すれば並びは変わらないため、答えは Yes です。

アルゴリズム

次の手順で判定します。

1. 左から順に見て、最初に \(p_i \neq q_i\) となる位置 \(L\) を探す。
2. もしそのような位置が存在しなければ、すでに \(p = q\) なので Yes。
3. 右から順に見て、最初に \(p_i \neq q_i\) となる位置 \(R\) を探す。
4. 区間 \([L, R]\) を反転したときに \(q\) と一致するか確認する。

反転後、元の \(p_i\) は位置 \(L + R - i\) に移動します。

したがって、すべての \(i\) について

\(p_i = q_{L+R-i}\)

が成り立てば、区間 \([L, R]\) を反転することで一致します。

コードではこの条件を確認しています。

for (int i = L; i <= R; i++) {
    if (p[i] != q[L + R - i]) {
        cout << "No\n";
        return 0;
    }
}

すべて一致すれば Yes を出力します。

計算量

• 時間計算量: \(O(N)\)
• 空間計算量: \(O(N)\)

実装のポイント

配列の添字はコード中では \(0\) 始まりで扱っています。

また、\(p\) と \(q\) が最初から完全に一致している場合も、操作は「ちょうど \(1\) 回」必要ですが、\(L = R\) の反転を選べば並びは変わらないため Yes になります。

ソースコード

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    cin >> N;

    vector<int> p(N), q(N);
    for (int i = 0; i < N; i++) cin >> p[i];
    for (int i = 0; i < N; i++) cin >> q[i];

    int L = 0;
    while (L < N && p[L] == q[L]) L++;

    if (L == N) {
        cout << "Yes\n";
        return 0;
    }

    int R = N - 1;
    while (R >= 0 && p[R] == q[R]) R--;

    for (int i = L; i <= R; i++) {
        if (p[i] != q[L + R - i]) {
            cout << "No\n";
            return 0;
        }
    }

    cout << "Yes\n";
    return 0;
}

---

この解説は gpt-5.5-xhigh によって生成されました。