[백준] 33901 - OR이 아니면? XOR (Python)

https://www.acmicpc.net/problem/33901

import sys
from collections import defaultdict
input = sys.stdin.readline

n, m, k = map(int, input().split())
a = list(map(int, input().split()))

ans = 0
window = defaultdict(int)
for i in range(n):
    ans += window[a[i]^k]
    window[a[i]] += 1
    window[a[i-m]] -= (i>=m)

print(ans)

• 제약조건: $(2 \le N \le 10^6;$ $1 \le M \le N - 1;$ $0 \le K \le 2^{17} - 1)$
• 시간제한: 1초

1) 탐색

브루트포스로 (i, j)쌍을 모두 탐색하면 O(n*m)으로 시간초과가 뜬다. 슬라이딩윈도우를 사용하면 O(n)으로 해결 가능하다.
defaultdict로 window를 선언하고 리스트 a를 인덱스 i로 순회하면서 사이즈 m인 윈도우 내에서 a의 각 원소가 몇번 등장하는지 카운팅한다.

2) XOR 연산의 성질

a[i]^a[j]==k를 만족하는 쌍을 찾아야 하는데, XOR연산은 다음이 성립한다.

X^Y=Z
X^Z=Y
Y^Z=X

그래서 위 코드의 for루프에서 window(a[i]^K)는 현재 윈도우 내에서 해당 a[j]가 등장한 적이 있는지를 체크한다. (슬라이딩 윈도우 내에 없는 경우 defaultdict이므로 ans에 0이 더해진다.)

뱀발

https://ko.wikipedia.org/wiki/XOR_%EA%B5%90%EC%B2%B4_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98