길이가 같은 두 수열 $s$와 $t$가 다음의 연산을 원하는 만큼 반복해 서로 같아질 수 있다면, 두 수열은 서로 이븐하다.
길이 $N$의 수열 $A$가 주어진다. $A[l,r]=[A_{l},A_{l+1},\dots,A_{r}]$을 $A$의 $l$번째 원소부터 $r$번째 원소까지만을 포함하는 연속된 부분 수열이라고 할 때, 다음 조건을 만족시키는 $A[l,r]$의 최대 길이를 구해보자.
$m=\left\lfloor\frac{l+r}{2}\right\rfloor$에 대하여, $A[l,m]$과 $A[m+1,r]$이 서로 이븐하다.
첫 번째 줄에 수열 $A$의 길이인 정수 $N$이 주어진다. $(1\leq N \leq 5\,000)$
두 번째 줄에 수열 $A$의 원소를 나타내는 $N$개의 정수 $A_{1},A_{2},\dots,A_{N}$이 공백으로 구분되어 주어진다. $\left(1\leq A_i \leq 10^{9}\right)$
연속된 부분 수열 $A[l,r]$을 절반으로 나눠 얻은 두 수열이 서로 이븐할 때, $A[l,r]$의 최대 길이를 출력한다.
만약 그러한 연속된 부분 수열이 존재하지 않는다면, $0$을 출력한다.
3
1 1 1
2
5
1 2 3 2 3
4
브루트포스, 집합, 좌표 압축, 슬라이딩 윈도우 등 PS에서 자주 나오지는 않지만 알아 두어야 할 필수 개념들을 모두 엮어서 만들어낸 상당히 참신한 문제.
일단, naive하게 생각하면 $O\left(N^3\right)$의 풀이가 존재함을 빠르게 확인할 수 있다. 그러나 $N$의 크기가 최대 5,000임을 생각해 보면 봉인하는 게 좋을 것이다. 결국, 이 문제의 목표는 $O\left(N^2\right)$의 풀이를 찾는 것이다.
일반적으로 이러한 형태의 문제는 슬라이딩 윈도우를 적용하는 게 보편적이다. 이 문제도 비슷하게 슬라이딩 윈도우를 적용하는 방식을 생각해 볼 수 있다. 중요한 건 그 방법인데, 그전에, $A\lfloor l, r\rfloor$의 길이가 홀수일 수 있을까? 절대 불가능하다. $A\lfloor l, r\rfloor$의 길이는 반드시 짝수이어야 한다. 따라서, 모든 $i$에 대해 $A\lfloor i, i+1\rfloor$에서부터 시작하여 길이를 양쪽으로 한 칸씩 늘려 가면서 찾아야 한다.
문제는, 그렇게 해도 $O\left(N^3\right)$을 벗어나기가 어렵다. 그래서, 여러 가지 방법의 최적화를 생각해 볼 수 있다.