概要

2つの順列 \(p, q\) について、連続区間を1回だけ反転して \(p\) を \(q\) にできるかを判定する問題です。
一致していない最初と最後の位置を見つけ、その区間が「逆順対応」しているかを確認すれば判定できます。

考察

重要な観察は次の通りです。

• 1回の区間反転で変化するのは、ある区間 \([L, R]\) の中だけ
• したがって、\(p\) と \(q\) が異なる位置は連続した1区間にまとまっていなければならない
• 具体的には、
  • 左から見て最初に異なる位置を \(l\)
  • 右から見て最初に異なる位置を \(r\) とすると、反転候補区間は実質 \([l, r]\) に決まる

このとき必要条件は
- 区間外はすでに一致（これは \(l, r\) の定義で満たされる） - 区間内は反転対応：\(p[l+i] = q[r-i]\) がすべての \(i\) で成り立つ

これをそのままチェックすれば十分です。

素朴解法が厳しい理由

全ての \((L, R)\) を試すと \(O(N^2)\) 通りあり、各回反転後比較に \(O(N)\) かかると最悪 \(O(N^3)\) で到底間に合いません（\(N \le 10^6\)）。
この問題は「不一致区間は1つに定まる」という性質を使って、1回の走査で解くのがポイントです。

アルゴリズム

1. 左から走査して、最初に \(p[l] \ne q[l]\) となる位置 \(l\) を探す。
2. もし見つからなければ（全要素一致）、\(L=R\) の操作で「ちょうど1回」を満たせるので Yes。
3. 右から走査して、最初に \(p[r] \ne q[r]\) となる位置 \(r\) を探す。
4. 区間 \([l, r]\) について、ポインタ \(i=l, j=r\) として
   • すべての位置で \(p[i] == q[j]\) を確認しつつ \(i++, j--\)。
   • 1つでも崩れたら No。
5. 最後まで通れば Yes。

例

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

• 最初の不一致 \(l=2\)（0-index）
• 最後の不一致 \(r=4\)
• 比較:
  • \(p[2]=5\) と \(q[4]=5\)
  • \(p[3]=4\) と \(q[3]=4\)
  • \(p[4]=3\) と \(q[2]=3\)
• すべて一致 → Yes

計算量

• 時間計算量: \(O(N)\)
• 空間計算量: \(O(N)\)（入力配列の保持）

実装のポイント

• 「全一致」のときに Yes を返すのを忘れない（\(L=R\) で1回操作したことにできる）。

• 反転対応チェックは p[i] と q[j] の比較で行う（実際に反転配列を作る必要はない）。

• 配列は 0-index で実装されているので、境界条件（i <= r など）に注意。

  ソースコード

#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;

    int i = l, j = r;
    while (i <= r) {
        if (p[i] != q[j]) {
            cout << "No\n";
            return 0;
        }
        ++i;
        --j;
    }

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

---

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