1113C Sasha and a Bit of Relax. 며칠전에 있었던 Codeforces Round #539 (Div.2)의 문제다. 이건 같은 날에 열린 Div.1의 A번 문제이기도 했다. XOR 관련 문제는 금방 풀 거라고 매번 착각하고 매번 어렵다. 이번에도 Editorial을 봤다…

다른 사람들의 풀이를 보면 아슬아슬하게 통과하긴해도 초당 10¹⁰ 정도는 지장이 없었던것 같다. 보통 잡는 1억이라는 수치는 꽤 보수적으로 잡은 수치고, for문 한 번 돌 때의 연산이 무거운게 아니기 때문에 그럴 수 있겠다.

XOR 연산의 특징을 이용해서 pref_r == pref_l-1 인 부분은 이해했는데 홀짝을 배열로 만들어서 저장하는건 바로 이해를 못했다. 홀짝으로 나눠서 저장한 이유는 문제에서 제시한 대로 r+l-1이 짝수기 때문이다.

cnt[1][0] = 1인 이유는 아래 예를 하나 들어주면 이해가 금방 될 것이다. cnt[1][0] = 0이라고 두고 아래 코드를 돌려보자. cnt[1][0] = 0이면 맨 처음에 funny pair 가 만들어져서 1을 더해야하는 상황에서 0을 더하기 때문이다.

2
5 5
=====
output: 0
answer: 1

5
2 2 1 5 3
=====
output: 0
answer: 1

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());
        int[][] cnt = new int[2][(1 << 20) + 1];

        cnt[1][0] = 1;
        long ans = 0;
        int cur = 0;
        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i = 0; i < n; i++) {
            cur ^= Integer.parseInt(st.nextToken());
            ans += cnt[i&1][cur]++;
        }

        System.out.println(ans);
    }
}

다른 사람들의 코드를 보다가 좀 신기한? 코드를 봤다. 시프트 하는 걸 풀어쓴 것도 신기하고 저 코드가 굉장히 빨랐다는 것도 신기하고 저렇게 생각한 것도 신기했다. https://codeforces.com/contest/1113/submission/50011763

이 문제에서 쓰인 XOR 특징

XOR은 같은 수를 연산하면 0이 나오는 특징이 있다. XOR 연산으로 swap 구현하는 것을 떠올려보자. 두 숫자의 주소가 같아서 0으로 나오는 경우(swap이 안되는 경우)를 생각해보면, 같은 수를 XOR하면 0이라는 것을 쉽게 까먹지 않는다.

그래서 a_l ⊕ a_l+1 ⊕ … ⊕ a_mid = a_mid+1 ⊕ … ⊕ a_r-1 ⊕ a_r 이면, a_l ⊕ … ⊕ a_r = 0 이다.

아래 특징은 대칭키 암호를 떠올리면 쉽게 까먹지 않는다.