[Codeforces] Manipulating History

https://codeforces.com/problemset/problem/1688/C

https://codeforces.com/problemset/problem/1688/C

문제 풀이방법도 어려웠지만, 문제 이해도 힘들었다...흑흑

 

최초의 문자로부터 시작해서 순서가 존재하는 시퀀스 $t$를 홀수 원소를 짝수 원수로 교체(replace)한다. 이렇게 교체한 후 final string인 $s$을 만든다. input data에서 $t$는 shuffle되어 제시된다.

 

처음에는 Brute Force하게 최초의 문자를 정하고, t 배열도 정렬해야하나 싶었다.

하지만 힌트에 의하면 그렇게 일일이 시도할 필요가 없다고 한다.

 

Hint 1.

You do not need to know anything about string matching or other algorithms.

 

Hint 2.

Why the initial string consists of only one letter?

 

Hint 3.

Why the answer is unique if there is at least one answer?

 

Hint 4.

What if each string in the input data consist of one letter?

 

Hint 5.

Parity.

 

최초의 문자열은 단 하나의 문자로 전제된다.

만약 특정 문자가 최초의 문자이면, 대체 여부를 떠나서 input data의 대체되는 string, 대체하는 string, final string에 홀수 번 등장한다.

만약 최초의 문자가 아니라면, 대체되는 string과 대체하는 string에서 짝을 지어 문자가 등장하므로 짝수 번 등장한다.

 

그래서 홀수 번 등장하는 문자만 알아내기 위해 XOR 연산을 사용하였다.

즉 이렇게 브루트포스를 사용하지 않아도 된다.

#include <iostream>

using namespace std;


int main() {
    int T;
    cin >> T;
    
    while(T--) {
        int n;
        char c = 0;
        cin >> n;
        n = 2 * n + 1;
        while(n--) {
            string s;
            cin >> s;
            for(auto x : s) {
                c ^= x;
            }
        }
        cout << c << '\n';
    }
}