원문 PDF 의 글을 화면용으로 옮겼습니다. 내용이 다르면 원문이 맞습니다. (검수일 2026-11-20)
수열 연산
원제: 수열 연산
문제
길이가 인 수열 과 길이가 인 수열 이 주어진다.
수열 는 개의 정수 을 각각 정확히 한 번씩 원소로 가지는 순열이다. 수열 의 각 원소는 이상 이하이고, 모든 원소가 서로 다르다.
여러분이 연산을 가할 수열을 라고 하자. 처음에 수열 는 수열 와 동일하다. 여러분은 수열 에 다음 두 종류의 연산을 회 이상 원하는 만큼 수행할 수 있다.
- 교환 연산 라고 하자. 이고 인 정수 를 골라, 인접한 두 원소 와 의 값을 서로 바꿀 수 있다.
- 합치기 연산 라고 하자. 인 정수 를 골라, 인접한 두 원소 와 을 하나의 원소 로 합칠 수 있다. 즉, 이 연산을 수행하면 수열 의 길이가 감소한다.
주어진 연산들을 이용하여 수열 를 수열 와 같게 만들 수 있는지 판정하라. 만약 가능하다면, 수열 를 수열 로 바꾸는 연산열을 아무거나 하나 찾아라.
연산의 개수를 최소화할 필요는 없음에 유의하라.
제약 조건
- 주어지는 모든 수는 정수이다.
- 수열 는 의 순열이다. 즉,
- 정수 ()에 대하여
- 의 값은 모두 서로 다르다.
부분문제
- (7점)
- (8점)
- (12점)
- (10점) 정수 ()에 대하여
- (13점)
- (15점) 수열 는 수열 의 부분수열이다. 즉, 을 만족하면서 모든 정수 ()에 대하여 인 정수 이 존재한다.
- (30점)
- (5점) 추가 제약 조건 없음.
입력 형식
첫 줄에 두 정수 과 이 공백으로 구분되어 차례대로 주어진다.
그다음 줄에 개의 정수 이 공백으로 구분되어 차례대로 주어진다.
그다음 줄에 개의 정수 이 공백으로 구분되어 차례대로 주어진다.
출력 형식
수열 를 수열 로 만들 수 없다면, 첫 줄에 NO를 출력한다.
수열 를 수열 로 만들 수 있다면, 아래와 같이 출력한다.
첫 줄에 YES를 출력한다.
그다음 줄에 수행할 연산의 개수 를 출력한다. 는 다음 조건을 만족해야 한다.
그다음 개의 줄에 수행할 연산을 순서대로 출력한다. 각 연산은 다음 두 형식 중 하나이다.
1 i수열 의 번째 원소와 번째 원소에 대해 교환 연산을 수행한다. 이 연산을 수행하기 직전의 수열 의 길이를 라고 할 때, 이고, 수열 의 번째 원소의 값이 번째 원소보다 작아야 한다.2 i수열 의 번째 원소와 번째 원소에 대해 합치기 연산을 수행한다. 이 연산을 수행하기 직전의 수열 의 길이를 라고 할 때, 여야 한다.
모든 위치는 해당 연산을 수행하기 직전의 수열 를 기준으로 하며, 수열의 첫 번째 위치는 번으로 한다.
출력한 모든 연산을 순서대로 수행한 결과는 수열 와 정확히 같아야 한다.
가능한 출력이 여러 개라면 그중 아무거나 하나를 출력해도 정답으로 인정된다.
주어진 연산들을 이용하여 수열 를 수열 로 만들 수 있다면, 위 조건을 모두 만족하는 출력이 존재함을 증명할 수 있다.
예제
예제 1
4 2 1 4 2 3 3 1
YES 6 1 1 1 2 1 3 2 1 1 1 2 2
수열 는 다음과 같이 변한다.
따라서 수열 를 수열 로 만들 수 있다.
예제 2
2 1 1 2 2
NO
예제 3
4 4 3 2 1 4 3 1 2 4
NO
예제 4
4 2 1 3 2 4 1 3
NO