F. Swaps Again (Codeforces Round #648 Div. 2)

問題

https://codeforces.com/contest/1365/problem/F

問題概要

長さnの数列a, bが与えられる。

aに対して以下の操作を任意の回数行うことで、aをbに変換できるかどうか答えよ

• のkを一つ選ぶ
• aの長さkのprefixとsuffixを交換する

自分の考察

操作前に対称の位置にある項は、いかなる操作をしても同じ側に来ない、という観点から実装しました。

が、これでは条件が不十分で合いません。

正しい解法

同じ側に来ないだけでなく、常に対称の位置をキープし続ける、がより強い条件としてありました。

に対して との各ペアは、操作によってお互いの位置が変わらないか、対称位置に居続けるかどちらかなのです。

なので、最初の配列aの上記の各ペアを保持しておいて、配列bでもそのペアが崩れていないかをチェックするだけでよかったのでした。

あ、nが奇数のときは、中心の項がaとbで同じかどうかを確認しなければなりません。中心の一つは他とペアになりませんし、移動もしません。

#include <bits/stdc++.h>
using namespace std;
 
int main() {
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        vector<int> a(n);
        vector<int> b(n);
        for (int i = 0; i < n; i++) cin >> a[i];
        for (int i = 0; i < n; i++) cin >> b[i];

        // nが奇数の時、中心をチェック
        if (n % 2 == 1 and a[n / 2] != b[n / 2]) {
            cout << "No" << endl;
            continue;
        }

        // aの各ペアを保持
        multiset<pair<int, int>> s;
        for (int i = 0; i < n / 2; i++) s.emplace(min(a[i], a[n - 1 - i]), max(a[i], a[n - 1 - i]));

        bool ok = true;
        for (int i = 0; i < n / 2; i++) {
            pair<int, int> x = {min(b[i], b[n - 1 - i]), max(b[i], b[n - 1 - i])};
            auto itr = s.find(x);
            if (itr == s.end()) {
                ok = false;
                break;
            }
            s.erase(itr);
        }
        cout << (ok ? "Yes" : "No") << endl;
    }
}

個人的反省

最初に思いついた考察に固執してしまうのはよくないですね。一歩踏み込んで考えられるようにならないとだめです。