📝 문제 정보#
번역#
문제#
“바늘"은 북쪽 왕국에 사는 전설적인 암살자이다. 알다시피, 바늘은 매우 가늘고 길다. 무엇보다, 치명적으로 날카롭다. 북쪽 왕국의 왕은 바늘이 수없이 찔러 자신을 죽일지도 모른다는 생각에 사로잡혀 있다. 왕은 바늘을 체포하라는 긴급 명령을 내렸다. 그리하여 바늘은 남쪽 왕국으로 탈출하기로 결심했다.
아래 그림과 같이, 두 왕국 사이의 국경은 세 개의 수평 장벽(선분)으로 이루어져 있으며, 각 장벽에는 하나 이상의 극소 크기의 구멍이 뚫려 있다. (구멍은 그림에서 $\times$로 표시되어 있다.) 세 장벽은 길이가 같으며 그림과 같이 수직으로 나란히 정렬되어 있다. 위쪽 장벽은 가운데 장벽보다 1단위 위에, 가운데 장벽은 아래쪽 장벽보다 1단위 위에 위치한다. 두 왕국은 뚫을 수 없는 외벽으로 둘러싸여 있다. 각 왕국의 영토는 매우 넓어서, 바늘은 왕국 안에서 자유롭게 움직일(평행 이동 또는 회전) 수 있다. 바늘의 길이는 장벽 길이의 최소 두 배 이상이다. 바늘은 강체, 즉 구부러지지 않으며 두께가 없으므로, 구멍은 자유롭게 통과할 수 있지만 구멍 이외의 장벽 부분은 뚫을 수 없다.
북쪽 왕국에서 남쪽 왕국으로 가는 유일한 방법은, 세 장벽 각각의 구멍 하나씩을 동시에 통과하는 것이다. 즉, 바늘은 세 장벽에서 각각 하나씩, 총 세 개의 구멍이 일직선 위에 놓여 있을 때에만 국경을 통과할 수 있다. 그림의 국경에서는 북쪽에서 남쪽으로 가는 탈출 통로가 두 개 존재한다.
이 불쌍한 암살자를 위해, 북쪽 왕국에서 남쪽 왕국으로 가능한 탈출 통로의 수를 구하는 프로그램을 작성하라.
입력#
표준 입력으로부터 읽는다. 입력은 여섯 줄로 구성된다. 첫 번째 줄에는 위쪽 장벽의 구멍 수를 나타내는 양의 정수 $n_u$가 주어진다. 두 번째 줄에는 구멍들의 $x$좌표를 나타내는 $n_u$개의 정수가 공백으로 구분되어 주어진다. 세 번째와 네 번째 줄은 가운데 장벽에 대한 것으로, 각각 가운데 장벽의 구멍 수 $n_m$과 $n_m$개의 구멍의 $x$좌표가 주어진다. 다섯 번째와 여섯 번째 줄은 아래쪽 장벽에 대한 것으로, 각각 아래쪽 장벽의 구멍 수 $n_l$과 $n_l$개의 구멍의 $x$좌표가 주어진다. $1 \leq n_u, n_m, n_l \leq 50{,}000$이며, 모든 구멍의 $x$좌표는 $-30{,}000$ 이상 $30{,}000$ 이하의 정수이다. 각 장벽의 구멍들은 서로 다른 $x$좌표를 가진다.
출력#
표준 출력으로 출력한다. 정확히 한 줄을 출력한다. 북쪽에서 남쪽으로 가능한 모든 통로의 수를 나타내는 음이 아닌 정수를 출력하라.
🧐 관찰 및 접근#
- 윗쪽, 가운데, 아랫쪽에서 숫자 하나씩을 골랐을때, 등차수열을 이루면 되는 것 같다.
- 윗쪽, 아랫쪽을 더해서 만들 수 있는 수들중에, 가운데 수의 두배가 되는 경우의 수를 찾자.
- 더하는걸 나이브하게 하면 $O(N^2)$, 두 수를 고르고 이분탐색하거나 하면 $O(N^2\log N)$이지만..
- 차수로 생각하면 $x$ 좌표의 범위에 대해 $O(X\log{X})$에 될 것 같다.
💻 풀이#
- 코드 (C++):
void solve(){
int n1; cin >> n1;
vector<int> v1(n1);
rep(i, 0, n1) cin >> v1[i];
int n2; cin >> n2;
vector<int> v2(n2);
rep(i, 0, n2) cin >> v2[i];
int n3; cin >> n3;
vector<int> v3(n3);
rep(i, 0, n3) cin >> v3[i];
vector<cd> A(131072), B(131072);
for(int x: v1) A[x+30000] = 1;
for(int x: v3) B[x+30000] = 1;
FFT::fft(A);
FFT::fft(B);
rep(i, 0, 131072) A[i] *= B[i];
FFT::fft(A, true);
int ans = 0;
for(int x: v2) ans += round(A[(x+30000)<<1].real());
cout << ans << '\n';
}