NYPC 2021 본선 1519부문 3번 풀이 (BOJ 23347)

대회장에선 섭태 1만 긁고 접근도 못했는데 백준에 올라왔길래 업솔빙을 했습니다.

서브태스크 2와 3의 풀이를 urd05님에게 듣고 100점 풀이를 찾았습니다.

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

23347번: 수열 연산

실제 대회에서의 서브태스크는 다음과 같습니다.

서브태스크 1: $2M \le K$

서브태스크 2: $M, K, |C|, |D| \le 6$

서브태스크 3: $M, K, |C|, |D| \le 10$

서브태스크 4: $M, K, |C|, |D| \le 30$

서브태스크 5: $M, K, |C|, |D| \le 50$

 

문제에서 쓸 수 있는 추가 쿼리와 삭제 쿼리를 다음과 같이 표기하겠습니다.

$add(idx, S)$: 인덱스 $idx$에 집합 $S$를 오름차순 정렬하여 삽입한다.

$delete(idx, n)$: 구간 $[idx, idx+n)$을 삭제한다.

 

편의를 위해 다음 집합을 정의하겠습니다.

$S_{all} = \left\{ 1, 2, \cdots, K \right\}$

서브태스크 1

인덱스 $idx$에 있는 수 $x$를 삭제하는 함수 $delete\_number(idx, x)$를 다음과 같이 구현할 수 있습니다.

 

Case 1: $x \le \frac{K}{2}$일 때

$add \left(idx+1, \left \{ x+1, x+2, \cdots, K \right \} \right)$

$delete(idx, K-x+1)$

({x} -> {x x+1 x+2 ... K} -> {})

 

Case 2: 나머지 경우

$add \left(idx, \left \{ 1, 2, \cdots, x-1 \right \} \right)$

$delete(idx, x)$

({x} -> {1 2 ... x-1 x} -> {})

 

입력으로 주어지는 수열 $C$와 $D$에 대해, 위 방식으로 각 수열의 원소를 모두 제거해준 다음, $D$를 제거할 때 호출했던 쿼리들의 순서와 부호(추가/삭제)를 모두 뒤집어주면 답이 된다는 것을 알 수 있습니다.

 

서브태스크 2

$M$이 커지게 되면 서브태스크 1에서 사용했던 전략을 쓸 수 없게 됩니다. 일단 몇 가지 쉬운 경우부터 생각해봅시다.

 

Case 1: $K<M$인 경우

이 경우에는 어떤 쿼리도 사용할 수 없습니다. 따라서 $C$와 $D$가 같은지만 확인해주면 됩니다.

 

Case 2: $K=M$인 경우

서브태스크 1에서 했던 것처럼 $C$와 $D$ 각각의 길이를 최대한 줄여봅시다. 추가하거나 삭제할 수 있는 수열은 $1, 2, \cdots, K$로 유일하기 때문에 수열 전체를 돌면서 $1, 2, \cdots, K$를 계속 제거해주면 수열의 길이를 최소화할 수 있고, 동일한 길이의 다른 수열은 만들 수 없음을 알 수 있습니다. (자세한 증명은 생략하겠습니다.)

 

따라서, $C$와 $D$ 각각의 길이를 최소화시킨 다음 수열이 일치한다면 YES, 다르다면 NO를 출력하면 됩니다.

방법 출력은 서브태스크 1에서 했던 것처럼 $C$는 그대로 출력하고 $D$는 사용한 쿼리들의 순서와 부호를 모두 뒤집어서 출력해주면 됩니다.

 

Case 3: $K>M$인 경우

놀랍게도 이 경우는 항상 YES입니다. $K=M-1$인 경우를 해결할 수 있다면, $K>M-1$인 경우도 동일하게 풀어주면 되기 때문에 $K=M-1$일 때의 풀이만 설명하겠습니다.

 

서브태스크 1에서 했던 것처럼 $delete\_number(idx, x)$함수를 구현할 수 있다면 문제를 해결할 수 있습니다.

 

인덱스 $idx$에 있는 수 $x$를 삭제하는 함수 $delete\_number(idx, x)$와 인덱스 $idx$에 수 $x$를 추가하는 함수 $add\_number(idx, x)$를 다음과 같이 구현할 수 있습니다.

 

$delete\_number(idx, x)$:

    $add(idx, S_{all} - \left\{ x \right\})$

    for $i = x+1$ to $K$:

        $delete\_number(idx+x-1, i)$

    for $i = x+1$ to $K$:

        $add\_number(idx+i-1, i)$

    $delete(idx, K)$

 

({x} -> {1 2 ... x-1 x+1 ... K x} -> {1 2 ... x-1 x} -> {1 2 ... x-1 x x+1 ... K} -> {})

 

$add\_number(idx, x)$도 동일한 방식으로 구현해주면 됩니다.

 

$x$를 제거할 때 호출하는 쿼리의 개수는 $2 \times 3^{K-x}$이므로, 최대 쿼리 횟수는 $2 \times 3^5 \times 6 \times 2 = 5832$이 되기 때문에 서브태스크 2를 통과할 수 있습니다.

 

서브태스크 3

$3^{10}=59049$이므로 서브태스크 2의 풀이로는 서브태스크 3을 풀 수 없습니다.

서브태스크 2에서 재귀호출을 하는 부분을 생각해보면 $x$를 제거할 때 $x+1, \cdots, K$를 호출하기 때문에 1을 제거하려면 너무 많은 재귀호출이 발생합니다.

 

$delete\_number(idx, x)$의 구현을 약간 바꿔봅시다.

 

$delete\_number(idx, x)$:

    $add(idx+1, S_{all} - \left\{ x \right\})$

    for $i = 1$ to $x-1$:

        $delete\_number(idx+1, i)$

    for $i = 1$ to $x-1$:

        $add\_number(idx+i-1, i)$

    $delete(idx, K)$

 

({x} -> {x 1 2 ... x-1 x+1 ... K} -> {x x+1 ... K} -> {1 2 ... x-1 x x+1 ... K} -> {})

 

위 구현을 사용하면 $x$를 제거할 때 $1, \cdots, x-1$을 호출하게 됩니다. 따라서, $\frac{K}{2}$이하인 수는 $x$를 감소시키는 방향, 나머지 수는 $x$를 증가시키는 방향으로 구현해주면 쿼리 횟수가 $O(K3^{\frac{K}{2}})$가 되기 때문에 서브태스크 3을 맞을 수 있습니다.

(최악의 경우 쿼리 횟수 $2 \times 3^{4} \times 10 \times 2 = 3240$)

 

서브태스크 4

제한이 30이 되었기 때문에 더 이상 지수복잡도로는 해결이 불가능해 보입니다.

쿼리 횟수가 지수복잡도가 되는 이유를 생각해보면 $x$를 제거할 때 $x+1, \cdots, K$를 재귀호출하기 때문에 횟수가 지수적으로 증가하게 됩니다.

그렇기 때문에 $x+1, \cdots, K$를 각각 제거하지 않고, 한 번에 제거해보겠습니다.

 

구간 $[idx, idx+K-x-1)$에 $x, x+1, \cdots, K$이 차례대로 있을 때, 이를 제거하는 함수 $delete\_suffix(idx, x)$를 다음과 같이 구현할 수 있습니다.

 

$delete\_suffix(idx, x)$:

    $add(idx, S_{all} - \left\{ x \right\})$

    if $x<K$:

        $delete\_suffix(idx+x-1, x+1)$

    $delete(idx, K)$

 

({x x+1 ... K} -> {1 2 ... x-1 x+1 ... K x x+1 ... K} -> {1 2 ... x-1 x x+1 ... K} -> {})

 

동일한 방식으로 suffix를 추가하는 $add\_suffix(idx, x)$도 구현할 수 있습니다.

 

$delete\_suffix(idx, x)$의 쿼리 횟수는 $2(K-x+1)$이므로 $delete\_number(idx, x)$의 쿼리 횟수는 $4(K-x)+2$가 됩니다.

최악의 경우 $(4 \times (30-1)+2) \times 30 \times 2 = 7080$번 쿼리를 호출하기 때문에 서브태스크 4를 맞을 수 있습니다. 

 

서브태스크 5

서브태스크 4 풀이로 구현하면 최악의 경우 쿼리 횟수가 $(4 \times (50-1)+2) \times 50 \times 2 = 19800$이 됩니다.

서브태스크 3에서 사용했던 아이디어를 가져와서, x가 작을 때는 suffix 대신 prefix를 제거하고 추가하는 방식으로 구현을 해주면 상수를 절반으로 줄일 수 있습니다.

 

이때, 최악의 경우는 수열의 모든 원소가 25 또는 26인 경우고, 쿼리 횟수를 계산해보면 $(4 \times (50-26)+2) \times 50 \times 2 = 9800$이 되어 문제를 해결할 수 있습니다.

 

구현

#include <bits/stdc++.h>

typedef long long ll;
using namespace std;
struct Query{
    char op;
    int i, len;
    vector<int> v;
    Query(){}
    Query(char _op, int _i, vector<int>::iterator _s, vector<int>::iterator _e): op(_op), i(_i) {
        for (auto iter = _s;iter!=_e;iter++) v.push_back(*iter);
        len = v.size();
    }
    void convert(){
        if (op=='+') op = '-';
        else op = '+';
    }
};
vector<Query> Q1, Q2;
vector<int> a, b, _all, _all_1[101];
int K, M, A, B;

void _add(vector<int> &C, int idx, vector<int> &D, vector<Query> &Q){
    Q.emplace_back('+', idx, D.begin(), D.end());
    C.insert(C.begin()+idx, D.begin(), D.end());
}

void _delete(vector<int> &C, int idx, int num, vector<Query> &Q){
    Q.emplace_back('-', idx, C.begin()+idx, C.begin()+idx+num);
    C.erase(C.begin()+idx, C.begin()+idx+num);
}

void _delete_suffix(vector<int> &C, int idx, int num, vector<Query> &Q){
    _add(C, idx, _all_1[num], Q);
    if (num<K) _delete_suffix(C, idx+num-1, num+1, Q);
    _delete(C, idx, K, Q);
}

void _add_suffix(vector<int> &C, int idx, int num, vector<Query> &Q){
    _add(C, idx, _all, Q);
    if (num<K) _add_suffix(C, idx+num-1, num+1, Q);
    _delete(C, idx, K-1, Q);
}

void _delete_prefix(vector<int> &C, int idx, int num, vector<Query> &Q){
    _add(C, idx+num, _all_1[num], Q);
    if (num>1) _delete_prefix(C, idx+num, num-1, Q);
    _delete(C, idx, K, Q);
}

void _add_prefix(vector<int> &C, int idx, int num, vector<Query> &Q){
    _add(C, idx, _all, Q);
    if (num>1) _add_prefix(C, idx+num, num-1, Q);
    _delete(C, idx+num, K-1, Q);
}

void solve1(vector<int> &C, vector<Query> &Q){
    for (int i=(int)C.size()-1;i>=0;i--){
        int x = C[i];

        if (x>K/2){
            _add(C, i, _all_1[x], Q);
            if (x<K){
                _delete_suffix(C, i+x-1, x+1, Q);
                _add_suffix(C, i+x, x+1, Q);
            }
            _delete(C, i, K, Q);
        }
        else{
            _add(C, i+1, _all_1[x], Q);
            if (x>1){
                _delete_prefix(C, i+1, x-1, Q);
                _add_prefix(C, i, x-1, Q);
            }
            _delete(C, i, K, Q);
        }

    }
}

void solve2(vector<int> &C, vector<Query> &Q){
    while(true){
        bool flag = 0;
        for (int i=0;i+K<=(int)C.size();i++){
            bool flag2 = 1;
            for (int j=1;j<=K;j++) if (C[i+j-1]!=j) {flag2 = 0; break;}
            if (flag2){
                flag = 1;
                _delete(C, i, K, Q);
                break;
            }
        }
        if (!flag) break;
    }
}

void output(){
    reverse(Q2.begin(), Q2.end());
    for (auto &q:Q2) q.convert();

    printf("YES\n%d\n", (int)Q1.size()+(int)Q2.size());
    for (auto &q:Q1){
        printf("%c %d %d ", q.op, q.i, q.len);
        if (q.op=='+'){
            for (auto &x:q.v) printf("%d ", x);
        }
        printf("\n");
    }
    //printf("------------------------------------------\n");
    for (auto &q:Q2){
        printf("%c %d %d ", q.op, q.i, q.len);
        if (q.op=='+'){
            for (auto &x:q.v) printf("%d ", x);
        }
        printf("\n");
    }
}

int main(){
    scanf("%d %d", &K, &M);
    scanf("%d", &A);
    a.resize(A);
    for (int i=0;i<A;i++) scanf("%d", &a[i]);
    scanf("%d", &B);
    b.resize(B);
    for (int i=0;i<B;i++) scanf("%d", &b[i]);

    for (int i=1;i<=K;i++){
        _all.push_back(i);
        for (int j=1;j<=K;j++) if (i!=j) _all_1[j].push_back(i);
    }

    if (K<M){
        if (a==b) printf("YES\n0\n");
        else printf("NO\n");
        return 0;
    }
    else if (K>M){solve1(a, Q1);solve1(b, Q2);}
    else {
        solve2(a, Q1); solve2(b, Q2);
        if (a!=b) {printf("NO\n"); return 0;}
    }
    output();
    return 0;
}