https://codeforces.com/contest/1516/problem/B
시간 1초, 메모리 256MB
input :
- t (1≤t≤15)
- n (2≤n≤2000)
- a1 , a2, …, an (0≤ai<2^30)
output :
- all elements equal while leaving at least 2 elements standing, print "YES". Otherwise, print "NO".
- 최소한 2개의 원소를 남기는데 이 때 모든 값이 동일하다면 "YES"를 아니면 "NO"를 출력하라.
조건 :
- he picks 2 adjacent elements; he then removes them and places a single integer in their place: their bitwise XOR. Note that the length of the array decreases by one.
- 2개의 인접한 원소를 골라 XOR연산을 수행한 뒤 그 값을 배열에 넣는다.
출력
일단 출력 값부터 다시 생각해보자.
2개 이상의 원소를 남기는데 그 때 이 원소들의 값이 동일하다면 이 조건이다.
예시에서의 0 2 2 뿐 아니라 3 3 3도 답에 해당한다는 의미이다.
연산
그러면 인제 XOR을 어떻게 수행할 것인가를 생각해 보자.
배열의 중간에서 XOR을 수행한다고 해서 배열의 제일 앞에서 부터 XOR 연산을 한 것과 그 결과 값이 다를까?
이에 대한 답은 그렇지 않다이다. 조건에 인접한 두 원소라는 문장이 존재하므로 그렇다.
그래서 이에 대한 방안으로 우리는 배열의 처음 값 부터 계속 XOR 연산을 하며 그 마지막 값을 확인 할 것이다.
이 때 연산을 마친 값이 0이라면 우리는 무슨일이 있어도 정답을 만들 수 있다. XOR이 0이 된다는 말은 동일한 원소에 대해 연산을 수행했다는 의미이기 때문이다.
그렇다면 3 3 3은 어떻게 해야 할까.
이 경우 XOR 연산을 마친 값이 0이 아니어도 정답이 된다는 의미인데. 여전히 우리는 연산 값을 가지고는 있다.
그리고 배열의 연산값을 나눈다고 생각을 하면 우리는 답을 얻을 수 있다.
xor 연산을 수행 하다 xr(xor 연산을 모두 수행한 값이 저장되어 있음)과 비교를 통해 동일하다면 cnt를 늘리면서 segment들을 나누는 것이다. xor연산 시 xr값을 내뱉는 부분 집합들로
이를 통해 우리는 cnt >= 3 이라면 정답이 된다는 것을 볼 수 있다.
- 그런 생각을 하고 있었다. cnt는 3이상인데 그 뒤에 만약
3 3 3 7같이 부분집합을 만들 수 있다면? 근데 말도 안되는 소리 였다. 일단 이렇게 나오려면 xr을 3으로 가정했다는 것인데 xr이 3이 되려면 이 값은3 3 3 0이 되어야 xor 연산 시에 이 값을 얻을 수 있다. 고로 생각할 필요가 없다.
