알고리즘
경로가 존재할 필요충분조건은 이 짝수이고 다음 등식이 성립하는 것이다.
이 조건을 만족하지 않으면 No를 출력한다. 만족하면 Yes를 출력하고 다음 순서로 이동한다.
U로 번 이동하여 에 도착한다.가능한 경우에는 개의 문자를 출력하므로 시간 복잡도는 이고, 불가능한 경우에는 이다. 전체 입력에 대한 시간 복잡도는 이다.
증명
홀수 크기에서는 사이클을 만들 수 없다.
격자점을 의 홀짝에 따라 두 색으로 칠하자. 한 번 이동할 때마다 색이 바뀌므로, 시작점으로 돌아오는 경로의 길이는 짝수여야 한다. 모든 점을 한 번씩 방문하는 사이클의 길이는 이므로 은 짝수여야 한다.
가능한 사이클의 넓이는 모두 같다.
수평 또는 수직인 길이 의 격자 선분끼리 교차하거나 겹치려면 격자점 하나를 공유해야 한다. 시작점으로 돌아오는 마지막 방문 외에는 점을 다시 방문하지 않으므로, 조건을 만족하는 사이클은 단순 다각형을 이룬다.
서브태스크 1
에서는 방문한 점들을 기록하며 가능한 모든 경로를 완전탐색할 수 있다. 모든 점을 방문한 뒤 한 번 더 이동하여 시작점으로 돌아갈 수 있으면, 신발끈 공식으로 그 경로의 넓이를 계산한다. 구한 경로들을 넓이별로 저장하면 주어진 에 맞는 경로를 찾을 수 있다.
첫 이동 이후에는 직전에 방문한 점으로 돌아갈 수 없으므로, 경로를 확장하는 각 단계에서 고려할 방향은 최대 개이다. 한 크기 에 대한 탐색 시간은 이다. 가능한 크기가 뿐이므로 각 크기에 대해 한 번씩 탐색한 결과를 재사용한다.
RDUD로 한 번 이동한 뒤, L로 번 이동한다.다각형은 정사각형 안에 놓인다. 따라서 다각형의 내부에 있는 정수 격자점은 에 속해야 한다. 그런데 의 모든 점을 사이클이 방문하므로 모든 점이 다각형의 경계 위에 있다. 즉, 내부의 격자점 수는 이다.
경계는 길이 의 격자 선분 개로 이루어져 있고, 경계의 서로 다른 격자점 수도 이다. 픽의 정리에 따라 넓이는 다음과 같다.
따라서 목표 넓이 는 이 값과 같아야 한다.
짝수 크기에서는 위 구성으로 모든 점을 방문한다.
첫 단계는 인 열 전체를 방문한다. 가운데 단계는 부터 까지의 각 열에서 부터 까지의 점들을 번갈아 내려가거나 올라가며 방문한다. 이 점들은 서로 다르고 첫 단계에서 방문한 점들과도 겹치지 않는다.
이 짝수이므로 마지막 열에서는 아래로 이동하여 에 도착한다. 마지막 단계는 아직 방문하지 않은 인 행의 점들을 지나 시작점으로 돌아온다. 따라서 시작점으로 돌아오는 마지막 방문을 제외하면 모든 격자점을 정확히 한 번씩 방문한다.
총 이동 횟수는 다음과 같다.
이 사이클의 넓이는 앞에서 증명한 값과 같으므로, 제시한 조건은 충분조건이기도 하다.
Solution written by GPT6