007 - XOR Operations Puzzle　解説

実行時間制限: 2sec / メモリ制限: 1024 MB

解説

　この問題は、XORに関しての階差数列を考えることで見通しが良くなります。数列 $A$ の隣接する要素のXORをとった、長さ $N-1$ の数列 $D^A$ を $D^A_i = A_i \oplus A_{i+1}$ と定義します。同様に数列 $B$ についても $D^B$ を定義します。まず、操作によって両端の要素 $A_1$ と $A_N$ は決して変化しないため、$A_1 \neq B_1$ または $A_N \neq B_N$ の場合は一致させることができず、答えは -1 となります。

　次に、操作 $A_i \gets A_{i-1} \oplus A_{i+1} \oplus A_i$ が差分数列 $D^A$ に与える影響を考えます。操作後の新しい差分を計算すると、以下の２つの差分のみが変化し、他の差分は変化しません。 $${D^A}'_{i-1} = A_{i-1} \oplus (A_{i-1} \oplus A_{i+1} \oplus A_i) = A_i \oplus A_{i+1} = D^A_i$$ $${D^A}'_i = (A_{i-1} \oplus A_{i+1} \oplus A_i) \oplus A_{i+1} = A_{i-1} \oplus A_i = D^A_{i-1}$$ すなわち、操作は、階差数列 $D^A$ における隣接する2要素 $D^A_{i-1}$ と $D^A_i$ のスワップに他なりません。

　したがって、この問題は隣接スワップのみを用いて数列 $D^A$ を $D^B$ に一致させるための最小操作回数を求める問題に完全に帰着されます。これは、$D^A$ と $D^B$ の要素の多重集合が一致するか（ソートして一致するか）を判定した上で、一致する場合は $D^A$ を $D^B$ に並べ替えるための転倒数（Inversion Number）を求めることで解くことができます。転倒数は Binary Indexed Tree (Fenwick Tree) を用いることで $O(N \log N)$ で計算可能です。

コード例

以下はC++による想定解法のコードです。

                            C++
                        

                            #include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <queue>

using namespace std;

// Binary Indexed Tree (Fenwick Tree)
struct BIT {
    int n;
    vector<int> tree;
    BIT(int n) : n(n), tree(n + 1, 0) {}
    
    void add(int i, int x) {
        for (i++; i <= n; i += i & -i) tree[i] += x;
    }
    
    int sum(int i) {
        int s = 0;
        for (i++; i > 0; i -= i & -i) s += tree[i];
        return s;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int N;
    if (!(cin >> N)) return 0;
    
    vector<int> A(N), B(N);
    for (int i = 0; i < N; ++i) cin >> A[i];
    for (int i = 0; i < N; ++i) cin >> B[i];
    
    // 両端が一致するか確認
    if (A[0] != B[0] || A[N - 1] != B[N - 1]) {
        cout << -1 << "\n";
        return 0;
    }
    
    // XOR差分数列を構築
    vector<int> DA(N - 1), DB(N - 1);
    for (int i = 0; i < N - 1; ++i) {
        DA[i] = A[i] ^ A[i + 1];
        DB[i] = B[i] ^ B[i + 1];
    }
    
    // 多重集合として一致するか確認
    vector<int> sorted_DA = DA;
    vector<int> sorted_DB = DB;
    sort(sorted_DA.begin(), sorted_DA.end());
    sort(sorted_DB.begin(), sorted_DB.end());
    if (sorted_DA != sorted_DB) {
        cout << -1 << "\n";
        return 0;
    }
    
    // DBにおける各値の出現位置を記録
    map<int, queue<int>> posB;
    for (int i = 0; i < N - 1; ++i) {
        posB[DB[i]].push(i);
    }
    
    // DAの各要素がDBのどの位置に対応するか(順列P)を構築
    vector<int> P(N - 1);
    for (int i = 0; i < N - 1; ++i) {
        P[i] = posB[DA[i]].front();
        posB[DA[i]].pop();
    }
    
    // 転倒数を計算
    BIT bit(N - 1);
    long long ans = 0;
    for (int i = 0; i < N - 1; ++i) {
        ans += i - bit.sum(P[i]);
        bit.add(P[i], 1);
    }
    
    cout << ans << "\n";
    
    return 0;
}
                        