概要

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

考察

この問題を解くための重要なポイントは、反転すべき区間の候補を絞り込むことです。

1. すでに一致している場合

もし最初から \(p\) と \(q\) が完全に一致している場合、問題文の「\(L=R\) の場合は並びは変化しませんが、これも 1 回の操作を行ったものとみなします」というルールにより、どの位置でも良いので \(L=R\) として操作を行えば目標を達成できます。したがって、この場合は常に Yes です。

2. 一致していない場合

\(p\) と \(q\) が異なる場合、少なくとも 1 箇所以上の要素が異なっています。 反転操作によって \(p\) を \(q\) に一致させるためには、「\(p\) と \(q\) が異なっている全ての範囲」を反転させる必要があります。

具体的には、以下の手順で反転候補となる区間 \([L, R]\) を特定できます。 - 左端から見ていき、最初に \(p_i \neq q_i\) となるインデックスを \(L\) とする。 - 右端から見ていき、最初に \(p_i \neq q_i\) となるインデックスを \(R\) とする。

もし 1 回の反転で一致させることが可能なら、反転すべき区間はこの \([L, R]\) 以外にありえません。なぜなら： - \(L\) より左や \(R\) より右の要素を反転に含めてしまうと、元々一致していた要素が別の場所に移動してしまいます。 - \(p\) と \(q\) は順列（1から \(N\) が1回ずつ現れる）であるため、一度一致している場所を動かして別の要素を持ってくると、そこは必ず不一致になってしまいます。

したがって、「特定した区間 \([L, R]\) を反転させた後、配列全体が \(q\) と一致するか」を確認するだけで判定が可能です。

アルゴリズム

1. 配列 \(p\) と \(q\) を読み込む。
2. 左から順に比較し、最初に \(p[i] \neq q[i]\) となるインデックス \(L\) を探す。
3. 全て一致していれば、Yes を出力して終了する。
4. 右から順に比較し、最初に \(p[i] \neq q[i]\) となるインデックス \(R\) を探す。
5. \(p\) の \(L\) 番目から \(R\) 番目までの要素を反転させる。
6. 反転後の \(p\) が \(q\) と完全に一致するかを確認する。一致すれば Yes、そうでなければ No を出力する。

計算量

\(N\) が最大 \(10^6\) と大きいため、効率的な処理が必要です。 - 時間計算量: \(O(N)\) - 配列の走査（\(L, R\) の特定）、反転、および最後の比較はすべて \(O(N)\) で行えます。 - 空間計算量: \(O(N)\) - 長さ \(N\) の配列を 2 つ保持するために必要です。

実装のポイント

• \(N=10^6\) のため、入出力がボトルネックにならないよう C++ では ios_base::sync_with_stdio(false); cin.tie(NULL); を使用して高速化を行います。

• std::reverse(p.begin() + L, p.begin() + R + 1); を使うことで、指定した範囲を効率よく反転できます。

• vector 同士の比較 p == q は \(O(N)\) で行えるため、反転後のチェックに便利です。

  ソースコード

#include <iostream>
#include <vector>
#include <algorithm>

/**
 * Problem: Determine if a permutation p can be transformed into permutation q
 * by reversing exactly one contiguous subarray [L, R].
 * 
 * Approach:
 * 1. If p and q are already identical, we can perform an operation where L = R.
 *    This satisfies the "exactly 1 operation" condition and leaves the array unchanged.
 *    Therefore, if p == q, the answer is "Yes".
 * 2. If p and q are different, let L_min be the first index where p[i] != q[i]
 *    and R_max be the last index where p[i] != q[i].
 * 3. Any single reversal that transforms p into q must cover at least the range [L_min, R_max].
 * 4. Since p and q are permutations (all elements are distinct), any reversal that 
 *    includes elements outside [L_min, R_max] would swap elements that already match, 
 *    making them no longer match (unless the segment is trivial, which brings us back to [L_min, R_max]).
 * 5. Thus, we only need to check if reversing the specific segment [L_min, R_max] in p results in q.
 * 
 * Complexity:
 * - Time: O(N), where N is the number of students (up to 10^6).
 * - Space: O(N) to store the permutations.
 */

using namespace std;

int main() {
    // Fast I/O is necessary for N = 10^6
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N;
    if (!(cin >> N)) return 0;

    // Read the current order p
    vector<int> p(N);
    for (int i = 0; i < N; ++i) {
        cin >> p[i];
    }

    // Read the target order q
    vector<int> q(N);
    for (int i = 0; i < N; ++i) {
        cin >> q[i];
    }

    // Find the first index L where p and q differ
    int L = -1;
    for (int i = 0; i < N; ++i) {
        if (p[i] != q[i]) {
            L = i;
            break;
        }
    }

    // If there are no differences, p == q.
    // An operation with L = R (e.g., L=1, R=1) is allowed and results in p == q.
    if (L == -1) {
        cout << "Yes" << endl;
        return 0;
    }

    // Find the last index R where p and q differ
    int R = -1;
    for (int i = N - 1; i >= 0; --i) {
        if (p[i] != q[i]) {
            R = i;
            break;
        }
    }

    // The only candidate operation that could potentially transform p into q
    // is reversing the segment from index L to R.
    reverse(p.begin() + L, p.begin() + R + 1);

    // After performing the reversal, check if the entire array p matches q.
    // In C++, comparing two vectors takes O(N) time.
    if (p == q) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }

    return 0;
}

この解説は gemini-3-flash-thinking によって生成されました。