Boj 13428 배열의 합

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

알고리즘: fft

풀이(대문자와 소문자가 의미하는 바가 다르다):

배열 a[i]와 b[i]를 각각 배열 A와 배열 B에서 i(0<=i<100000)가 나온 횟수로 하자.
두 배열 a, b에 대해 합성곱에서 두 수의 곱셈을 두 수 중 크지 않은 것(c++에서 min함수)으로 바꾼 식을 계산하면 풀 수 있다(단, 배열 a, b의 크기 n은 200000이상으로 하고 100000부터는 a[i]와 b[i]는 0으로 하자).

 

$c[j]=\sum_{i=0}^{n-1}min(a[i],b[j-i])$

 

나이브하게 계산하면 시간 복잡도는 $O(n^{2})$가 되고 시간초과가 난다. i와 j가 0 or 1일때 min(i,j)=i*j임을 이용하자. 
f(x)를 x가 양수면 1, 그렇지 않으면 0으로 정의하면 임의의 음이 아닌 정수 i, j<=k에 대해 $min(i,j)=\sum_{t=0}^{k-1}min(f(i-t),f(j-t))$이다(일반성을 잃지 않고 i<=j라 하면 우변을 전개했을 때 처음 i개의 항만 1이 되고 나머지는 0이 되므로 min(i,j)와 같다). 그러므로 $min(i,j)=\sum_{t=0}^{k-1}f(i-t)f(j-t)$이다. 
이는 각 수를 f(i),f(i-1),f(i-2)...,f(i-k)로 나타내어 합성곱으로 구할 수 있고, 배열 a, b에서 가장 큰 수를 k라 하면 합성곱을 구하는 배열의 크기는 n*k가 되고 fft로 합성곱을 구하면 시간복잡도는 $O(nklog(nk))$ 이다. 
하지만 k가 최대 100000이고 k가 100000일 때 시간복잡도는 $O(n^{2}log n)$가 되므로 시간초과가 난다. 

배열 a와 b에서 각각 배열의 모든 수의 합을 구하면 N이하이므로 배열 a와 b에서 k이상인 수의 개수는 각각 N/k개 이하이다. 그러므로 배열에서 k보다 큰 수를 k로 하여 합성곱으로 계산한 값에 k보다 큰 수에 대해 k를 빼서 나이브하게 계산한 값을 더하여 두 방법을 합칠 수 있다.
이 때 시간복잡도는 $O(nklog(nk)+(\frac{N}{k})^{2})$이고 N의 최댓값(100000)을 n(200000)으로 생각하면 $O(nklog(nk)+(\frac{n}{k})^{2})$이다. 여기서 적당한 k값을 이용해 시간을 최소화해야 한다.
1<=k<=n으로 제한하면 $O(log(nk))$를 $O(log(n^{2}))$으로 대체할 수 있다.

산술 기하 평균 부등식에 의해 $nklog(n^{2})+(\frac{n}{k})^{2}=nklogn+nklogn+\frac{n^{2}}{k^{2}} >=3\sqrt[3]{n^{4}log^{2}n}$이고 등호성립조건은 $k= \sqrt[3]{\frac{n}{logn}}$이다.
계산해보면 k=22.478정도로 나오므로 k가 20정도면 된다(실제로는 k가 5~10일때 시간이 빠르게 나왔다).
시간복잡도는 $O( \sqrt[3]{n^{4}log^{2}n} )$이다.