概要

現在の並び \(p\) からちょうど1回の区間反転操作で目標の並び \(q\) に一致させられるかを判定する問題です。

考察

重要な気づき

区間 \([L, R]\) を反転させた後に \(p\) が \(q\) と一致するためには、次の2つの条件が必要です：

1. 区間の外側: 反転されない部分では \(p_i = q_i\) が成り立つ必要がある
2. 区間の内側: 反転した部分が \(q\) と一致する必要がある

つまり、\(p\) と \(q\) が異なる位置は連続した区間でなければならず、その区間を反転すると \(q\) と一致しなければなりません。

具体例

\(p = [1, 5, 4, 3, 2, 6]\)、\(q = [1, 2, 3, 4, 5, 6]\) の場合：

• \(p\) と \(q\) が異なる位置は \(i = 1, 2, 3, 4\)（0-indexed）
• この区間 \([1, 4]\) の \(p\) の要素は \([5, 4, 3, 2]\)
• これを反転すると \([2, 3, 4, 5]\) となり、\(q\) の同じ区間 \([2, 3, 4, 5]\) と一致する
• よって答えは Yes

素朴なアプローチの問題

全ての \((L, R)\) の組を試して反転後に一致するか確認すると、\(O(N^2)\) かかり \(N \leq 10^6\) では TLE になります。

解決策

\(p\) と \(q\) が異なる位置の最左端 \(L\) と最右端 \(R\) を求めれば、反転すべき区間は \([L, R]\) に一意に定まります。あとはその区間だけ検証すればよいです。

アルゴリズム

1. \(p\) と \(q\) を比較し、\(p_i \neq q_i\) となる最小の \(i\) を \(L\)、最大の \(i\) を \(R\) とする
2. もし全ての位置で \(p_i = q_i\) なら（\(L\) が見つからない）、反転しなくても一致しているので Yes（\(L = R\) の操作で何も変わらない）
3. そうでなければ、\(p[L..R]\) を反転した結果が \(q[L..R]\) と一致するか確認する
   • 具体的には、全ての \(i\)（\(L \leq i \leq R\)）に対して \(p[L + R - i] = q[i]\) を確認
4. 一致すれば Yes、しなければ No

計算量

• 時間計算量: \(O(N)\) — 配列を最大2回走査するだけ
• 空間計算量: \(O(N)\) — 入力の格納に必要

実装のポイント

• \(L\) と \(R\) の探索は1回の走査で同時に行える（最初に見つかった不一致が \(L\)、最後に見つかった不一致が \(R\)）

• 反転の検証では、実際に配列を反転させる必要はなく、\(p[j]\)（\(j\) は \(R\) から \(L\) へ減少）と \(q[i]\)（\(i\) は \(L\) から \(R\) へ増加）を比較するだけでよい

• \(p = q\) の場合も「\(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 = -1, R = -1;
    for(int i=0;i<N;i++){
        if(p[i]!=q[i]){
            if(L==-1) L=i;
            R=i;
        }
    }
    
    if(L==-1){
        cout << "Yes" << endl;
        return 0;
    }
    
    // Check if reversing p[L..R] gives q
    for(int i=L, j=R; i<=R; i++, j--){
        if(p[j]!=q[i]){
            cout << "No" << endl;
            return 0;
        }
    }
    
    cout << "Yes" << endl;
    return 0;
}

---

この解説は claude4.6opus-thinking によって生成されました。