Saturday, January 18, 2014

acmicpc.net 8462 - 배열의 힘

문제 링크(acmicpc.net 8462)
자연수 n 개로 이루어진 배열 a1,a2,a3,,an이 있다.
l 부터 r  까지 부분 배열은 al,al+1,,ar 이다.
Ks는 부분 배열 안에 있는 자연수 s 의 개수이다.
부분 배열의 힘이란 모든 자연수 s 에 대해서, KsKss   를 합한 값이다.
배열과 부분 배열의 범위가 주어졌을 때, 각 부분 배열의 힘을 구하시오.

- 문제를 푸는 동안의 과정 -

1) 전체 길이 n의 배열을 루트 n 길이의 배열들로 나눈 다음에 각 쿼리에 대해서 좀 더 빠르게 처리하는 것이었다. O(NQ)보다는 좀 더 빠른 O(Q 루트 N)이었다. 하지만 TLE.

2) 쿼리를 가지고 어떻게 구하는 순서를 변형할 수 없을까 고민하였다. 주어진 쿼리가 (L(i), R(i))일 때, R(i)를 오름차순으로 정렬한 다음에 1)의 알고리즘과 같은 방법을 적용시켜보기로 했다. 그러면 R(i)에서 R(i+1)로 갈 때에는 더하는 일만 발생하고 L(i)에서 L(i+1)로만 갈 때, 빼는 일이 발생하므로 시간이 단축될 것 같았다. 물론 L(i)에서 L(i+1)로 가는 것보다 R(i+1)에서 L(i+1)로 가는 게 더 빠르면 후자를 택했다. 하지만 TLE.

3) 문제를 풀었던 이승재 선배(RiKang)랑 홍은기 선배(pichulia)의 도움을 받았다. 이 풀이법의 핵심은 쿼리를 sum( |R(i+1)-R(i)| + |L(i+1)-L(i)| )를 (상수)*(N 루트 N)과 가깝게 정렬하는 것이다. 그러면 인접한 쿼리에 대해서 그냥 선형적으로 훑으면서 부분 배열의 힘을 처리하여도 O(N 루트 N)에 가까운 시간복잡도가 된다.
정렬을 할 때, compare함수를 임의의 쿼리 L, R에 대해서 "(int)(L/루트(N))*루트(N)+(R/루트(N))"순으로 정렬하면 된다. 우선, 왜 그런지를 알기 전에 문제의 조건에 의해 L≤R임을 알아두자.
X = (int)(L/루트(N))*루트(N)이라 하면 각 X에 대해서 0 이상이면서 루트(N) 이하인 범위의 R을 참조할 수 있게 된다. 나중에 각 쿼리마다 부분배열의 힘을 계산하는 과정에서 소요되는 시간비용은 각 X에 대해서 O(max(X에서의 R(i))-min(X에서의 R(i)))가 된다. 따라서 총 시간복잡도는 O(X의 개수 * N) ≒ O(N 루트 N)이 된다.

참고로 Q(i)에서 Q(i+1)로 넘어갈 때 다음의 원리를 알면 부분배열의 힘을 선형시간 내에 계산할 수 있다. a에서 a+b가 될 때 a^2 에서 (a+b)^2가 된다. 여기서 차수가 2인 항에서는 2ab+b^2만이 추가되므로 b=1이라면 2a+1만이 증가하게된다.

Source Code

2 comments:

  1. 안녕하세요 05년도에 입학해서 작년에 대학원을 마치고 간 정통대의 살아 숨쉬던 화석 김재민입니다.. 위의 문제를 거의 똑같이 생각하여 소팅후 풀고 다시 인덱스로 원상복구 시켜서 출력하는 방법을 사용했는데 tle가 나오네요. 결과물들을 보면 3초 리밋에 0.3초 수준까지도 내는 사람들이 있는걸로봐서는 그정도 차이면 단순히 코드 몇줄 최적화 문제가 아니라 다른 풀이가 있는게 아닐까 하는 생각도 드는데.. 혹시 결과가 어느정도 시간에 accept 되었나요?

    ReplyDelete