https://www.acmicpc.net/problem/15501

아이디어

순열을 뒤집는 연산을 $F$, 왼쪽으로 미는 연산을 $L$, 오른쪽으로 미는 연산을 $R$이라 하자.

순서대로 연산들을 적용하는 것을 기호를 오른쪽으로 연이어 표시하자. 예를 들어 $FL$은 순열을 뒤집은 후 왼쪽으로 밀었음을 나타낸다.

이제 $F$, $L$, $R$ 사이에서 자명하게 성립하는 법칙들을 확인해보자.

1. 각 연산에는 반대 연산이 존재한다: $F^{-1}=F, L^{-1}=R, R^{-1}=L$
2. 순열을 2번 뒤집은 것은 원래의 순열과 같다: $FF = \mathrm{id}$
3. 왼쪽(오른쪽)으로 $n$번 미는 것은 원래의 순열과 같다: $L^n=R^n=\mathrm{id}$
4. 연산들 후 뒤집는 것은, 뒤집은 후 연산들을 반대로 하는것과 같다: $XF=FX^{-1}$

위의 법칙들을 통해 서로 다른 연산들의 조합은 다음 $2n$개의 조합 밖에 없음을 알 수 있다.
$\left\{\mathrm{id}, L, LL, \cdots, L^{n-1},\ \ F, LF, LLF, \cdots, L^{n-1}F\right\}$
그러므로, 알고리즘은 다음과 같이 생각해볼 수 있다.

순열을 왼쪽으로 밀고, 같은지 확인하는 과정을 $n$번 반복한 후, 같지 않았다면 뒤집어서 $n$번 더 시행해본다. 그래도 같지 않으면 두 순열을 같게 만들 수 없는 것.

코드 (Python)

from collections import deque

n = int(input())
p = deque(map(int, input().split()))
q = deque(map(int, input().split()))

for _ in range(n):
    q.rotate(-1)
    if p == q:
        print("good puzzle")
        exit(0)
r = deque([*q][::-1])
for _ in range(n):
    r.rotate(-1)
    if p == r:
        print("good puzzle")
        exit(0)
print("good puzzle" if p == q else "bad puzzle")

메모리 및 시간

• 메모리: 265948 KB
• 시간: 724 ms

개선 방법

• 굳이 모든 경우를 확인하지 않더라도, 첫번째 원소를 고정시킨 후 비교해도 된다.
  • $L^i$ 연산이 $L$을 $i$번 하는 것보다 빠를 것이므로...
• $F$, $L$, $R$로는 인접한 원소의 순서를 바꿀 수 없다는 사실을 이용해도 된다.
  • $F$는 왼쪽/오른쪽만, $L, R$은 원소의 절대적인 인덱스만 바꾼다.