https://www.acmicpc.net/problem/30828
문제 요약
- 숫자가 주어지고 쿼리가 주어짐
- (l, r) 구간에서 중복 없이 임의의 k 개를 골라 모두 xor한 값 + k 이 가장 큰 값을 구하면 됨
- N : 500, 숫자 : 0 ~ 511
접근법
- 임의의 k개를 골라서, xor을 구하고, k를 더하고... 연관성도 없어보이고 쿼리를 만들기도 어려워 보임
- 특정 구간이 정해진다고 해도 문제에서 요구하는 답을 구할 수 있을까?
- 500개 중에 k를 고르는 것만 해도 어려움
- N과 숫자의 범위가 지나치게 작은 것에 주목
- 우선 특정 구간에서 구해본다고 해보자
- 길이가 1, 2, 3, ... 마다 최대 값을 구할 수 있을까?
- 각각의 xor을 구하고 1을 더하고... 어려움
- xor해서 1, 2, 3, ... 511을 구할 수 있을까?
- 될 것 같음
- p - 1 까지 구해놓은 숫자들에 p 번째 숫자를 xor 하면 새로운 숫자 집합이 나올 것임(이런 비슷한 dp 문제들이 많음. 기타리스트?)
- 그런데 + 길이 처리를 어떻게 하나?
- xor해서 7이 나오는 길이가 여러개 있다고 하면, 그중에 가장 큰 값만 유효함.
- 즉 xor 값과 길이를 같이 구해나감
- 예를 들어 이전 까지 구한 xor 값들이 [1, 10, 17] 이고 각각을 만드는데 최대 길이가 [2, 3, 4] 라고 할때
- [1(2), 10(3), 17(4)] 처럼 표현할 수 잇음
- 현재 처리하는 숫자가 16이라고 하면 새로 만들어지는 xor 숫자 집합은 [1(2),10(3),17(4)], [16(1)], [1 xor 16, 10 xor 6, 17 xor 16] = [17(3),26(4),1(5)] 이 됨
- 이때 기존 1(2)는 1(5)로 갱신가능함(길이 4인 17과 길이 1인 16을 xor하면 길이 5인 1을 구할 수 있음)
- 또한 새로 구한 17(3)은 기존 17(4)보다 작기때문에 갱신하지 않음
- 이렇게 한번을 하면 특정 구간 (l,r)에 대해서 구할 수 있는 모든 xor과 각각의 최대 길이를 구할 수 있고, 구간 (l,r)의 최대값을 구할 수 있음
- 512 * k 번 연산 수행
- 모든 구간에 대해 수행하면 500 x 500 x 512 x k 번의 수행시간 필요, 대략 O(n^3)
newbieski