結果

問題 No.2018 X-Y-X
コンテスト
ユーザー qwewe
提出日時 2025-05-14 13:04:10
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
MLE  
実行時間 -
コード長 5,712 bytes
コンパイル時間 1,107 ms
コンパイル使用メモリ 97,360 KB
実行使用メモリ 813,996 KB
最終ジャッジ日時 2025-05-14 13:06:03
合計ジャッジ時間 3,747 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 4 MLE * 1 -- * 26
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <unordered_map> // Use unordered_map for potentially faster average time complexity
#include <vector> // Required for vector operations

using namespace std;

// Custom hash function structure for vector<int> to use it as a key in unordered_map.
// This is a common approach using XOR and bit shifts to combine element hashes.
struct VectorHasher {
    size_t operator()(const vector<int>& V) const {
        size_t hash = V.size();
        for(const auto &i : V) {
            // A common hash combining technique. 
            // The constant 0x9e3779b9 is related to the golden ratio and helps distribute hash values.
             hash ^= i + 0x9e3779b9 + (hash << 6) + (hash >> 2);
        }
        return hash;
    }
};


// Helper function to convert character 'A' or 'B' to integer 0 or 1.
// Using inline suggests the compiler to replace calls with function body if possible, potentially reducing overhead.
inline int char_to_int(char c) {
    // 'A' maps to 0, 'B' maps to 1
    return (c == 'B');
}

// Function to compute the difference array `d`.
// The k-th element d[k] (0-based index) represents whether S[k] and S[k+1] are different.
// d[k] = S_k XOR S_{k+1} (using 0/1 representation for A/B).
vector<int> compute_diff_array(const string& s) {
    int n = s.length();
    // The difference array has length N-1.
    vector<int> d(n - 1); 
    for (int i = 0; i < n - 1; ++i) {
        // Calculate difference using XOR on integer representations.
        d[i] = char_to_int(s[i]) ^ char_to_int(s[i+1]);
    }
    return d;
}


int main() {
    // Use fast I/O operations.
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n; // Length of the strings
    cin >> n;
    string s_str, t_str; // Input strings S and T
    cin >> s_str >> t_str;

    // A necessary condition for transformation is that the first and last characters must match.
    // These characters can never be changed by the operation.
    if (s_str[0] != t_str[0] || s_str[n - 1] != t_str[n - 1]) {
        cout << -1 << endl; // If they don't match, transformation is impossible.
        return 0;
    }

    // Compute the difference arrays for the initial string S and target string T.
    // The state transformation problem can be reformulated in terms of difference arrays.
    vector<int> d_s = compute_diff_array(s_str);
    vector<int> d_t = compute_diff_array(t_str);

    // If the difference arrays are already identical, no operations are needed.
    if (d_s == d_t) {
        cout << 0 << endl;
        return 0;
    }

    // Use Breadth-First Search (BFS) to find the shortest path in the state space.
    // The state is represented by the difference array.
    // `dist` stores the minimum distance (number of operations) from the initial state `d_s` to any reachable state.
    // `unordered_map` is used for efficient average time lookup of visited states.
    unordered_map<vector<int>, int, VectorHasher> dist; 
    queue<vector<int>> q; // Queue for BFS states to visit.

    dist[d_s] = 0; // Distance to the starting state is 0.
    q.push(d_s);   // Add the starting state to the queue.

    int final_dist = -1; // Initialize final distance to -1 (target not reached yet).

    // Standard BFS loop.
    while (!q.empty()) {
        vector<int> current_d = q.front(); // Get the current state (difference array).
        q.pop(); // Remove it from the queue.

        int current_dist = dist[current_d]; // Get the distance to the current state.

        // Check if the current state is the target state.
        if (current_d == d_t) {
            final_dist = current_dist; // Target found, record the distance.
            break; // Exit BFS since we found the shortest path.
        }

        // Explore neighbors by applying possible operations.
        // The operation involves choosing an index `i` from 1 to N-2.
        // The operation is possible if S[i] == S[i+2].
        // In terms of the difference array, this condition is equivalent to d[i-1] == d[i].
        // Note: String indices are 0 to N-1. Difference array indices are 0 to N-2.
        // Problem index i=1..N-2 corresponds to S[i], S[i+1], S[i+2].
        // Affects difference array at indices i-1 and i (0-based).
        for (int i = 1; i <= n - 2; ++i) { 
            // Check the condition d[i-1] == d[i]. Indices are 0-based.
            if (current_d[i-1] == current_d[i]) {
                vector<int> next_d = current_d; // Create a copy of the current state to modify.
                
                // The operation flips S[i+1]. This flips d[i-1] and d[i].
                // Flip the corresponding elements in the difference array copy.
                next_d[i-1] = 1 - next_d[i-1]; // Flip bit (0 becomes 1, 1 becomes 0)
                next_d[i]   = 1 - next_d[i];   // Flip bit
                
                // Check if the resulting state `next_d` has been visited before.
                // `find` checks existence. `dist.end()` means not found.
                if (dist.find(next_d) == dist.end()) { 
                    dist[next_d] = current_dist + 1; // Record the distance to the new state.
                    q.push(next_d); // Add the new state to the queue for exploration.
                }
                // If already visited, we ignore it because BFS guarantees that the first time we visit a state,
                // it is via a shortest path from the source.
            }
        }
    }

    // After BFS completes, output the found distance.
    // If `final_dist` is still -1, it means the target state `d_t` was unreachable.
    cout << final_dist << endl;

    return 0;
}
0