https://www.acmicpc.net/problem/33156
문제요약
- 수열의 구성이 서로 같으면 이븐함
- 주어진 수열의 부분 수열중에 왼쪽반, 오른쪽반이 서로 이븐한 부분 수열의 최대 길이 구하기
- N=5000, 원소 10^9
접근법
- N^2개의 부분수열을 구하고, 각각이 조건을 만족하는지 판단하는 것은 N^3이상임
- 부분수열의 중간을 먼저 지정하고, 양쪽이 서로 이븐한지를 판단하는 방식으로 접근함
- 어떤 중간으로부터 양쪽으로 범위를 키워나감
- 범위를 키워나가면서 왼쪽, 오른쪽을 map에 저장하면서 원소가 몇개인지 세어나감
- 왼쪽, 오른쪽의 카운팅이 같으면 서로 이븐한 것임
- 그런데 카운팅을 매번 비교 하면 매번 N의 시간이 걸릴 것임
- 그래서 변경된 것만 비교한다!
- 왼쪽이 추가될때 -> map +1
- 오른쪽이 추가될때 -> map -1
- map의 모든 원소가 0이면 서로 이븐
- +1, -1 이 있으면 서로 다름
- 그리고 +1 또는 -1인 것들의 개수를 셈 = diffcount
- +1 또는 -1이 발생할때마다 diffcount++
- 0이 발생할때마다 diffcount0--
- 확장을 한번하고 diffcount가 0이면 => 그 구간은 이븐하다
- 시간복잡도 N(중간) x N(범위확장) x logN(map 사용)
시간초과 개선
- python에서는 통과는 하는데(python 시간 버프)
- cpp에서는 실패 : map 사용 때문인 듯
- N이 5000이니까 좌표를 압축하고, map 대신 array 사용
newbieski