Monday, May 26, 2014

acmicpc.net 3103 - 순열의 순서

Problem Link

Croatian Highschool Competitions in Informatics 2010 Final Exam #1 - ASISTENT

1부터 K까지의 숫자로 이루어진 길이가 K인 순열 X에서 N개의 쿼리에 대해 A[i]번째와 B[i]번째(1 ≤ i ≤ N)의 숫자를 Swap한다. 각 쿼리에 대해서, 모든 가능한 순열을 정렬했을 때, 순열의 순서가 몇 번째인지 출력하는 문제이다.

우선, 어느 순열의 순서는 각 X[i]마다 (X[i]>X[j](i<j)인 j의 개수 : P(i)) × Factorial (K - i)을 더해줌으로써 구할 수 있다. (K log K)

A[i]번째와 B[i]번째를 스왑하는 경우를 생각해보자.

1 ... X(A[i]-1) X(A[i]) X(A[i]+1) ... X(B[i]-1) X(B[i]) X(B[i]+1) ... K

A[i]번째와 B[i]번째를 제외한 A[i]+1부터 B[i]-1번째까지의 P(j)들은 최대 1까지만 증가할 수 있다. 그리고 1~A[i]-1번째와 B[i]+1~K번째 P값은 변화가 없다. 따라서 X의 첫번째 원소부터 차례대로 보면서, P를 계산할 BIT와 Factorial을 계산할 BIT 2개를 update시켜주면서 각 쿼리에 가감해야할 값을 계산해주면 된다. 시간복잡도는 O(K log K + N log K).

Source Code

1 comment:

  1. 안녕하세요 이 문제 풀다가 잘 안풀려서ㅠㅠ 질문 좀 드려도 될까요? 어떻게 한 쿼리 당 log K로 해결할 수 있는 거죠 ?? 'A[i]번째와 B[i]번째를 제외한 A[i]+1부터 B[i]-1번째까지의 P(j)들은 최대 1까지만 증가할 수 있다. 그리고 1~A[i]-1번째와 B[i]+1~K번째 P값은 변화가 없다.'는 이해가 가는데 그 다음 문장이 이해가 안갑니다 ㅠㅠ

    ReplyDelete