BOJ 10531 Golf Bot (FFT)

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

10531번: Golf Bot

200000 이하의 숫자로 이루어진 집합이 주어진다. 이어서 어떤 수들이 주어졌을 때, 앞서 주어진 집합의 원소 하나 혹은 두 개의 합으로 질의된 수를 만들 수 있는지 구해야 한다.

Naive 방법

크기가 200000인 배열 A를 만들다. A[x] = 0 이면 집합에 x가 없고, A[x] = 1 이면 집합에 x가 있음을 말한다. 질의로 주어진 숫자 q에 대해서 모든 집합의 원소 a에 대해 A[q-a] = 1 이면, q는 주어진 집합의 원소 a와 q-a의 합으로 나타낼 수 있다. (A[0]=1로 하면 q == a인 경우를 처리할 수 있다)

위 방법은 각 질의에 대해 집합내의 모든 원소를 테스트해봐야 하므로, 질의당 시간복잡도가 O(n)이 되고 질의의 수 m회 실행해야 하므로 전체 시간복잡도는 O(nm)이 된다. n과 m이 모두 200000이하이기 때문에 TLE가 예상된다.

합성곱

집합 A와 B가 있고, A에서 임의의 원소 a, B에서 임의의 원소  b를 선택해서, q=a+b를 만들 수 있는지 물어보는 문제는 합성곱(Convolution)을 이용하여 구할 수 있다.

이산 합성곱(Convolution)연산은 아래와 같이 정의한다.

f*g(t) = sum { f[k] * g[t-k] }

c(t) = f*g(t) 라 하면 c[0] .. c[3]은 아래와 같다.

c[0] = f[0] * g[0]
c[1] = f[0] * g[1] + f[1] * g[0]
c[2] = f[0] * g[2] + f[1] * g[1] + f[2] * g[0]
c[3] = f[0] * g[3] + f[1] * g[2] + f[2] * g[1] + f[3] * g[0]

즉 합성곱의 결과 c[q]에는 합이 q가 되는 모든 숫자 쌍 x, y (x + y = q)에 대해 f[x]와 g[y]의 곱을 합한 값이 들어간다.

집합 A에 원소 a가 있으면 A[a] = 1, 없으면 A[a] = 0로 한다. 집합 B에 대해서도 동일하게 한다. 배열 A와 B의 합성곱 C를 구하면, C[t]는 t = a + b 인 모든 쌍 (a, b)에 대해서 A[a]도 1이고 B[b]도 1인 경우의 수가 된다. 즉 C[t] 는 a + b = t (a in A, b in B)가 되는 경우의 수이다.

배열 A와 B은 합성곱은 O(|A||B|)에 구할 수 있다.

고속 푸리에 변환(Fast-Fourier Transform, FFT)

고속 푸리에 변환을 이용하면 합성곱을 O(n log n)시간에 구할 수 있다.

시간 도메인에서 함성곱은 푸리에 도메인에서 일반곱에 대응되는 성질을 이용한다.

고속 푸리에 변환 알고리즘을 이용하면 이산 공간에서 시간 도메인과 푸리에 도메인 간의 변환과 역변환을 O(n log n) 시간에 할 수 있다.

https://codeforces.com/blog/entry/43499

Tutorial on FFT/NTT — The tough made simple. ( Part 1 ) - Codeforces

다시 문제로

다시 문제로 돌아와서, 골프 기계가 골프공을 x만큼 칠 수 있으면 A[x] = 1, 그렇지 않으면 A[x] = 0으로 나타낸다.

합성곱 C = A*A(t)를 구하면, C[q]는 x + y = q인 x와 y에 대해서, A[x] = 1이고 A[y] = 1인 경우, 즉 골프 기계가 x만큼도 보낼 수 있고, y만큼도 보낼 수 있는 경우의 수가 된다. C[q] > 0 이면 골프 기계를 두 번 이용하여 골프공을 q만큼 보낼 수 있다.

A[0] = 1로 하면, C[q]에 A[0] * A[q] = A[q]인 경우도 카운트하므로 골프 기계를 한 번만 사용한 경우도 포함한다.

 

비슷한 문제

• https://www.acmicpc.net/problem/17134