1665번: 화물열차
첫째 줄에는 화물 열차 A에 연속적으로 컨테이너가 놓여 있는 구간의 개수 N이 주어진다. 이어 N줄에는 Xi와 Yi (Xi ≤ Yi)가 공백을 사이에 두고 주어지는데 이는 화물 열차 A의 Xi칸부터 Yi칸까지 컨
www.acmicpc.net
문제 요약
길이가 최대 \(10^9\) 칸으로 기다란 두 화물 열차에 각각 \(N\leq1000\) 개, \(M\leq1000\) 개의 독립된 연속된 구간에 컨테이너들이 실려 있습니다. 이웃한 철도 위에 놓인 두 화물 열차 사이에서 짐을 옮기기 위해, 최대한 많은 컨테이너가 서로 맞닿도록 두 화물 열차를 두려고 합니다. 처음에 두 화물 열차의 첫 칸의 앞부분이 서로 맞닿아 있을 때, 한 화물 열차가 얼마나 많이 움직여야 최대한 많은 컨테이너들이 서로 맞닿을까요?
아래 내용은 문제의 풀이를 포함합니다.
문제 풀이
두 가지의 큰 관찰이 필요합니다.
- 화물 열차를 다항식으로서 나타낼 수 있다.
- 다항식을 \(x-1\)로 나눌 때, 누적 합으로써 각 항의 계수를 알 수 있다.
두 열차가 겹칠 때 두 열차에서 겹치는 칸의 번호의 합이 일정하며, 한 화물 열차가 이동한 거리에 따라 정해진다는 사실을 알 수 있습니다. 여기서 첫 번째 관찰을 할 수 있습니다.
첫 번째 관찰에서, 화물 열차의 컨테이너 하나를 항 하나로 표현할 것입니다. 예제의 화물 열차 A를 보면 1, 2, 3, 5, 7, 8, 9 번째 칸에 컨테이너가 놓여 있는데, 이를 다음과 같이 나타냅시다.
$$A(x)=x^9+x^8+x^7+x^5+x^3+x^2+x$$
마찬가지로, 화물 열차 B 또한 다음과 같이 나타냅시다.
$$B(x)=x^9+x^8+x^6+x^3+x^2$$
이렇게 나타냄으로써 좋은 점이 무엇일까요? \(A(x)B(x)\)를 봅시다.
$$A(x)B(x)=(x^9+x^8+x^7+x^5+x^3+x^2+x)(x^9+x^8+x^6+x^3+x^2)$$
$$=x^{18}+2x^{17}+2x^{16}+2x^{15}+2x^{14}+2x^{13}+2x^{12}+5x^{11}+4x^{10}+3x^9+2x^8+2x^7+x^6+2x^5+2x^4+x^3$$
여기서 각 항의 의미를 따져 보면, \(ax^{b+1}\)은 한 화물 열차를 \(b\) 칸 움직였을 때 \(a\) 개가 겹침을 뜻한다는 것을 쉽게 알 수 있습니다. 따라서, \(a\)가 최대인 가장 작은 \(b\)를 찾으면 그 값이 곧 답입니다.
그런데 두 다항식의 항이 최대 \(10^9\) 개입니다. 수가 너무 큽니다. 이는 다음 성질을 이용할 수 있습니다.
$$x^{n-1}+x^{n-2}+\cdots+x^2+x+1=\frac{x^n-1}{x-1}$$
이로써 \(A(x)\)와 \(B(x)\)의 항의 개수를 더 줄일 수 있습니다. 예제의 경우에는 다음과 같이 나타내어집니다.
$$A(x)=\frac{x^{10}-x^7+x^6-x^5+x^4-x}{x-1}$$
$$B(x)=\frac{x^{10}-x^8+x^7-x^6+x^4-x^2}{x-1}$$
두 식의 분자의 항의 개수는 각각 \(O(N)\), \(O(M)\)개입니다. 따라서 다음 꼴의 식을 \(O(NM\mathrm{log}NM)\) 시간 안에 구해도 충분합니다.
$$A(x)B(x)=\frac{x^{20}-x^{18}+3x^{13}-4x^{12}+x^9-x^8+2x^7-x^6-x^5+x^3}{(x-1)^2}$$
물론, 위 식의 분자의 항의 개수는 \(O(NM)\) 개입니다. 그런데, 위 식에서 답을 어떻게 얻을 수 있을까요? 여기서 두 번째 관찰을 할 수 있습니다.
다항식을 \(x-1\)로 나누는 모습을 상상해 봅시다. 하나의 항을 \(x-1\)로 나눌 때 생기는 일은 다음과 같습니다.
$$ax^b=ax^{b-1}(x-1)+ax^{b-2}(x-1)+\cdots$$ 위와 같이 \(a\)가 뒤 모든 항의 계수에 더해지는 것을 알 수 있습니다. 따라서, 답은 \(A(x)B(x)=\frac{f(x)}{(x-1)^2}\)일 때 \(f(x)\)의 계수들의 누적 합의 누적 합이 최대인 항의 지수를 구함으로써 알 수 있습니다.
시간 복잡도는 \(O(NM\mathrm{log}NM)\)입니다.
