3회 문제풀이 09 / ABC 150 C - Count Order

ABC 150 C - Count Order

【문제 개요】

크기 N의 순열(1, 2, …, N)를 정렬할 수 있는 수열(P, Q)가 있습니다.
크기 N의 순열의 종류는 N!개 입니다. 그 중, P가 사전순으로 a번째로 작고 Q가 사전순으로 b번째로 작을때 |a - b|를 구하시오.

• 2개의 수열 X, Y에 대해서 어떤 정수 k가 존재할때 Xi = Yi(1 ≦ i < k) 그리고 Xk < Yk가 성립할 때, X는 Y보다 사전적으로 작다고 정의한다.

【전제】

• 2 ≦ N ≦ 8
• P, Q는 크기 N의 순열이다.
• 입력은 전부 정수이다.

【입력 형태】

N
P1 P2 ... PN
Q1 Q2 ... QN

【출력 형태】

|a - b|를 출력하라.

【예시】

입력 예 1

3
1 3 2
3 1 2

출력 예 1

3

크기 3의 순열은 (1, 2, 3)、(1, 3, 2)、(2, 1, 3)、(2, 3, 1)、(3, 1, 2)、(3, 2, 1)의 6개가 있습니다. 그 중(1, 3, 2)는 사전순으로 2번째, (3, 1, 2)는 사전순으로 5번째이니까 정답은 |2 - 5| = 3이다.

입력 예 2

8
7 3 5 4 2 1 6 8
3 8 2 5 4 6 7 1

출력 예 2

17517

입력 예 3

3
1 2 3
1 2 3

출력 예 3

0

출처 : https://atcoder.jp/contests/abc150/tasks/abc150_c

ABC 150 C - Count Order

【문제 개요】

크기 N의 순열(1, 2, …, N)를 정렬할 수 있는 수열(P, Q)가 있습니다.
크기 N의 순열의 종류는 N!개 입니다. 그 중, P가 사전순으로 a번째로 작고 Q가 사전순으로 b번째로 작을때 |a - b|를 구하시오.

• 2개의 수열 X, Y에 대해서 어떤 정수 k가 존재할때 Xi = Yi(1 ≦ i < k) 그리고 Xk < Yk가 성립할 때, X는 Y보다 사전적으로 작다고 정의한다.

【전제】

• 2 ≦ N ≦ 8
• P, Q는 크기 N의 순열이다.
• 입력은 전부 정수이다.

【입력 형태】

N
P1 P2 ... PN
Q1 Q2 ... QN

【출력 형태】

|a - b|를 출력하라.

【예시】

입력 예 1

3
1 3 2
3 1 2

출력 예 1

3

크기 3의 순열은 (1, 2, 3)、(1, 3, 2)、(2, 1, 3)、(2, 3, 1)、(3, 1, 2)、(3, 2, 1)의 6개가 있습니다. 그 중(1, 3, 2)는 사전순으로 2번째, (3, 1, 2)는 사전순으로 5번째이니까 정답은 |2 - 5| = 3이다.

입력 예 2

8
7 3 5 4 2 1 6 8
3 8 2 5 4 6 7 1

출력 예 2

17517

입력 예 3

3
1 2 3
1 2 3

출력 예 3

0

출처 : https://atcoder.jp/contests/abc150/tasks/abc150_c