루미 알고리즘

#1138다이아수열 연산수열 연산

KOI 2026 2차코딩중등부 4번출제 장근영이 문제가 어렵다면 — 배우는 순서 보기

원문 PDF 의 글을 화면용으로 옮겼습니다. 내용이 다르면 원문이 맞습니다. (검수일 2026-11-20)

수열 연산

원제: 수열 연산

문제

길이가 NN인 수열 A=[A1,A2,⋯ ,AN]A = [A_1, A_2, \cdots, A_N]과 길이가 MM인 수열 B=[B1,B2,⋯ ,BM]B = [B_1, B_2, \cdots, B_M]이 주어진다.

수열 AA는 NN개의 정수 1,2,⋯ ,N1, 2, \cdots, N을 각각 정확히 한 번씩 원소로 가지는 순열이다. 수열 BB의 각 원소는 11 이상 NN 이하이고, 모든 원소가 서로 다르다.

여러분이 연산을 가할 수열을 XX라고 하자. 처음에 수열 XX는 수열 AA와 동일하다. 여러분은 수열 XX에 다음 두 종류의 연산을 00회 이상 원하는 만큼 수행할 수 있다.

  • 교환 연산 X=[X1,X2,⋯ ,XK]X = [X_1, X_2, \cdots, X_K]라고 하자. 1≤i≤K−11 \le i \le K - 1이고 Xi<Xi+1X_i < X_{i+1}인 정수 ii를 골라, 인접한 두 원소 XiX_i와 Xi+1X_{i+1}의 값을 서로 바꿀 수 있다.
  • 합치기 연산 X=[X1,X2,⋯ ,XK]X = [X_1, X_2, \cdots, X_K]라고 하자. 1≤i≤K−11 \le i \le K - 1인 정수 ii를 골라, 인접한 두 원소 XiX_i와 Xi+1X_{i+1}을 하나의 원소 min⁡(Xi,Xi+1)\min\left(X_i, X_{i+1}\right)로 합칠 수 있다. 즉, 이 연산을 수행하면 수열 XX의 길이가 11 감소한다.

주어진 연산들을 이용하여 수열 XX를 수열 BB와 같게 만들 수 있는지 판정하라. 만약 가능하다면, 수열 XX를 수열 BB로 바꾸는 연산열을 아무거나 하나 찾아라.

연산의 개수를 최소화할 필요는 없음에 유의하라.

제약 조건

  • 주어지는 모든 수는 정수이다.
  • 1≤M≤N≤3 0001 \le M \le N \le 3\,000
  • 수열 AA는 1,2,⋯ ,N1, 2, \cdots, N의 순열이다. 즉, {A1,A2,⋯ ,AN}={1,2,⋯ ,N}\{A_1, A_2, \cdots, A_N\} = \{1, 2, \cdots, N\}
  • 정수 ii (1≤i≤M1 \le i \le M)에 대하여 1≤Bi≤N1 \le B_i \le N
  • B1,B2,⋯ ,BMB_1, B_2, \cdots, B_M의 값은 모두 서로 다르다.

부분문제

  1. (7점) N≤8N \le 8
  2. (8점) M=1M = 1
  3. (12점) M=NM = N
  4. (10점) 정수 ii (1≤i≤N1 \le i \le N)에 대하여 Ai=iA_i = i
  5. (13점) M=N−1M = N - 1
  6. (15점) 수열 BB는 수열 AA의 부분수열이다. 즉, 1≤p1<p2<⋯<pM≤N1 \le p_1 < p_2 < \cdots < p_M \le N을 만족하면서 모든 정수 ii (1≤i≤M1 \le i \le M)에 대하여 Bi=ApiB_i = A_{p_i}인 정수 p1,p2,⋯ ,pMp_1, p_2, \cdots, p_M이 존재한다.
  7. (30점) N≤300N \le 300
  8. (5점) 추가 제약 조건 없음.

입력 형식

첫 줄에 두 정수 NN과 MM이 공백으로 구분되어 차례대로 주어진다.

그다음 줄에 NN개의 정수 A1,A2,⋯ ,ANA_1, A_2, \cdots, A_N이 공백으로 구분되어 차례대로 주어진다.

그다음 줄에 MM개의 정수 B1,B2,⋯ ,BMB_1, B_2, \cdots, B_M이 공백으로 구분되어 차례대로 주어진다.

출력 형식

수열 XX를 수열 BB로 만들 수 없다면, 첫 줄에 NO를 출력한다.

수열 XX를 수열 BB로 만들 수 있다면, 아래와 같이 출력한다.

첫 줄에 YES를 출력한다.

그다음 줄에 수행할 연산의 개수 QQ를 출력한다. QQ는 다음 조건을 만족해야 한다.

0≤Q≤N20 \le Q \le N^2

그다음 QQ개의 줄에 수행할 연산을 순서대로 출력한다. 각 연산은 다음 두 형식 중 하나이다.

  • 1 i 수열 XX의 ii번째 원소와 (i+1)(i + 1)번째 원소에 대해 교환 연산을 수행한다. 이 연산을 수행하기 직전의 수열 XX의 길이를 KK라고 할 때, 1≤i≤K−11 \le i \le K - 1이고, 수열 XX의 ii번째 원소의 값이 (i+1)(i + 1)번째 원소보다 작아야 한다.
  • 2 i 수열 XX의 ii번째 원소와 (i+1)(i + 1)번째 원소에 대해 합치기 연산을 수행한다. 이 연산을 수행하기 직전의 수열 XX의 길이를 KK라고 할 때, 1≤i≤K−11 \le i \le K - 1여야 한다.

모든 위치는 해당 연산을 수행하기 직전의 수열 XX를 기준으로 하며, 수열의 첫 번째 위치는 11번으로 한다.

출력한 모든 연산을 순서대로 수행한 결과는 수열 BB와 정확히 같아야 한다.

가능한 출력이 여러 개라면 그중 아무거나 하나를 출력해도 정답으로 인정된다.

주어진 연산들을 이용하여 수열 XX를 수열 BB로 만들 수 있다면, 위 조건을 모두 만족하는 출력이 존재함을 증명할 수 있다.

예제

예제 1

입력
4 2
1 4 2 3
3 1
출력
YES
6
1 1
1 2
1 3
2 1
1 1
2 2

수열 XX는 다음과 같이 변한다.

[1,4,2,3]→[4,1,2,3]→[4,2,1,3]→[4,2,3,1]→[2,3,1]→[3,2,1]→[3,1]\begin{aligned} [1, 4, 2, 3] &\to [4, 1, 2, 3] \\ &\to [4, 2, 1, 3] \\ &\to [4, 2, 3, 1] \\ &\to [2, 3, 1] \\ &\to [3, 2, 1] \\ &\to [3, 1] \end{aligned}

따라서 수열 XX를 수열 BB로 만들 수 있다.

예제 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

자료

출처 표기

출처: 한국정보올림피아드(KOI) 2026년 2차 대회 · 원문 페이지 · 이용 조건 CC BY-NC-SA 4.0 · 원문 그대로 실었으며 고치지 않았습니다.

크리에이티브 커먼즈 저작자표시-비영리-동일조건변경허락 4.0 국제. 비영리 목적으로만 이용할 수 있습니다.

문제 출처: 한국정보올림피아드(KOI) (CC BY-NC-SA 4.0) · International Olympiad in Informatics (IOI) (CC BY) · Centre for Education in Mathematics and Computing (CEMC), University of Waterloo (CC BY-NC 4.0) · Programmeringsolympiaden (CC BY-SA) · CSES Problem Set (Antti Laaksonen) (CC BY-NC-SA 4.0). 루미 알고리즘은 위 단체들과 관계없는 별도의 서비스이며, 자료는 원문 그대로 싣습니다. 문제마다 출처와 이용 조건을 따로 표기합니다.