2024 SW - IT Contest 문제 풀이

 

 

 

 

안녕하세요. 참가자 여러분들! 이번에도 운영진으로 참가한 황현석이라고 합니다. 반가워요!

 

이번에도 역시 출제자, 검수자 여러분들 수고 많았습니다! 제일 바쁘셨을 시온형도 고생많으셨습니다. 대다수의 문제 출제에 기여한 준원님도 고생 많으셨고요 ㅎㅎ

 

대회 끝나고, 집에와보니, 데이터가 약했다는 소식을 듣고, 씻지도 않고... 책상에 앉아 코드 좀 막고, 보강 좀 하느라, 녹초가 되었던 것 같습니다. 몸도 힘들고, 마음까지 뒹숭생숭하니까 정신이 없던 하루가 된 것 같아요. 거두절미하고 늦은 밤이라 풀이만 짧게 써보려고 합니다!

---

A. 햄버거

문자열 하나를 원하는 위치에 옮겨서, 햄버거 모양을 만드는데 필요한 최소한의 연산 횟수를 묻고 있습니다.

간단하게 구현하거나 특징을 찾아서 풀려는 시도가 있었는데, 저는 제일 깔끔하게, 모든 경우의 수에 따라, 정답을 출력하는 것이 베스트라고 생각합니다!

 

 

B. 다트판

Bob의 기댓값은 무조건 10.5점입니다! Alice의 기댓값은 20점 그리고 양옆의 점수의 평균이 됩니다! 이제 비교를 통해 정답을 출력해주기만 하면 되는 문제입니다!

 

 

C. ANA는 회문이야

유사 ANA 문자열의 정의를 보면, A로 시작해서 A로 끝납니다. 그 사이에 N이 존재하는 경우를 세면 되는 문제입니다.

 

제가 대회 중에 거의 모든 참가자분들의 코드를 읽고, 이해해 보려고 노력했었는데요. 대부분 for문을 돌리면서, A가 있을 때, flag를 세우고 한번 더 A를 만나면 작업을 시작하는 방식으로 풀이를 하셨더라고요!

 

저는 다소 시간을 잡아먹더라도, 더 아트하고 깔끔하게 떨어지는 풀이를 사용하는 것이 더 직관적이고 보기 좋다고 생각합니다.

 

#include<bits/stdc++.h>

using namespace std;

int N, ans;
string s;

int main () {
    cin >> N >> s;
    
    vector<int> vc;
    for (int i=0;i<N;i++) {
    	//vc 벡터에, A의 위치를 저장
        if (s[i] == 'A') vc.push_back(i);
    }

    for (int i=0;i<(int) (vc.size()) -1;i++) {
    	//A의 위치들 사이로 substring을 생성
        string temp = s.substr(vc[i], vc[i+1] - vc[i] +1);
        int k = 0;

        for (char c : temp) if (c == 'N') k++;

        if (k == 1) {
            ans++;
        }
    }

    cout << ans;
}

 

 

D. TPS

대부분의 참가자들의 첫 번째 통곡의 벽이 되었다고 생각됩니다. 저도 이 문제 보면서, 16개의 경우의 수를 케이스워크해서 푸는 참가자들이 나올 수도 있다고 생각했습니다. 그렇게 푸신 분들은 고생 많으셨습니다! 아래에는 조그마한 관찰을 통해, 구현량을 대폭 줄인 코드입니다.

 

일단 현재 플레이어의 위치와 바라보는 방향만 저장합니다! 플레이어가 이동할 때, dx, dy 인자값에 방향을 변수로 더해주면 간단하게 구현할 수 있습니다!

 

#include<bits/stdc++.h>

using namespace std;

int dy[4] = {1, 0, -1, 0}, dx[4] = {0, 1, 0, -1};
int direction, N, x, y;

map<string, int> mp;

int main () {
    cin >> N;
    mp["W"] = 0; mp["D"] = 1;
    mp["S"] = 2; mp["A"] = 3;

    while(N--) {
        string s; cin >> s;

        if (s == "MR") {
            direction += 1;
        } else if (s == "ML") {
            direction += 3;
        } else {
        	//방향도 같이 더해줍니다.
            x += dx[(direction + mp[s]) % 4];
            y += dy[(direction + mp[s]) % 4];
        }

        direction %= 4;
		//출력할 땐, 카메라 위치는 바라보는 방향의 반대쪽을 바로 구해줍니다.
        printf("%d %d %d %d\n", x, y, x + dx[(direction + 2) % 4], y + dy[(direction + 2) % 4]);
    }
}

 

 

E. 전구 주기 맞추기

$T$초에 정확히 전구가 불이 들어오기 위해선, 그 전구의 주기가, T의 약수일 필요가 있습니다.

$(T\text{'s divisor}) \times K = T$를 만족하는 $K$가 있기 때문입니다. 

 

그럼 $T$의 약수를 만들 때, 값이 적게 드는 방향으로 만들면 됩니다!

 

#include<bits/stdc++.h>

using namespace std;

int N, T;

int main () {
    cin >> N >> T;
    int answer = 0;

    while(N--) {
        int x; cin >> x;

        if (x >= T) {
            answer += x - T;
            continue;
        }
        int mn = 1e9;

        for (int i=x;i>=1;i--) if (T % i == 0) mn = min(mn, abs(x-i));
        for (int i=x;i<=T;i++) if (T % i == 0) mn = min(mn, abs(x-i));

        answer += mn;
    }

    cout << answer;
}

 

 

F. 일이 커졌어

일단 그리디 하게 관찰해 볼 수 있습니다. 수를 키우는 데에는, 곱하기가 더 유리합니다. 곱하기는 나중에 큰 수를 곱할수록 이득입니다. 더하기는 먼저 연산 한 수는 곱하기 영향을 더 받으니,. 먼저 큰 수를 받을수록 이득입니다.

 

이러면, 큰 수부터 차례로 그리디 하게 어디에 넣을지 바로 결정할 수 있습니다.

 

참가자 분들 또한, 구현 대다수가, 포문을 돌려서 for문 한 번에 특징을 찾아서 출력해 버리는 방식이 많았는데요. 사실 이런 류의 문제는 배열을 미리 선언 후에, 값을 집어넣고, 그 후 배열을 출력하는 게 제일 깔끔합니다!

 

수열을 만들거나 배열을 만들어야 하는 구성적 문제는 CodeForces나, Atcoder에서 굉장히 흔하게 등장하는 문제입니다.

배열을 미리 선언 후 출력 배열을 만들어 보는 방식을 채택해 보세요.

#include<bits/stdc++.h>

using namespace std;

int arr[101], N;

int main () {
    cin >> N;
    int nowNum = N;

    for (int i=N;i>=1;i--) {
        if (i % 2 == 1) {
            arr[i] = nowNum--;
        }
    }

    for (int i=1;i<=N;i++) {
        if (i % 2 == 0) {
            arr[i] = nowNum--;
        }
        
        //포문 하나 더 만들어서 출력해도 되지만, 저는 여기에 그냥 넣겠습니다
        cout << arr[i] << ' ';
    }
}

 

 

G. 배틀 로얄

G번부터 알고리즘 문제의 꽃인 시간 복잡도 처리와 자료구조를 사용해야 하는 문제가 나오기 시작했습니다.

 

조그마한 관찰을 해봅시다! 사람들의 최대 체력은 100만이고, 최소 대미지는 1입니다. 그러면, 사람들은 100만 번 언저리의 공격을 진행하면 무조건 한 명이 남습니다. 그럼, 최적화를 잘해서, 100만 번의 시뮬레이션만 딱 돌리게 하면 풀리겠네요!

 

자 일단 이중 포문을 사용해서, 배열을 돌면서, 살아남은 사람에 대해, 모든 사람들의 체력을 깎도록 풀면, 최악에 $O(N^3)$ 가 걸리게 됩니다.

 

이 부분은 사람들의 공격 대미지를 모아 놓는 변수 하나로 해결 가능합니다. 여태껏 사람들이 쌓아놓은 대미지를 합산하는 방식으로, 사람들에게 일일이 대미지를 주지 않아도, 한 번에 계산이 가능하게 됩니다.

 

그럼, 이제 포문으로 배열을 계속 돌면서, 계산해도 괜찮을까요? 여전히 $O(N^2)$입니다. 죽은 사람들을 계속 확인하고 지나치는 행위만으로도, 시간 손실이 굉장히 많이 난다는 것을 생각해 볼 수 있습니다.

 

죽은 사람들을 배열에서 빼면 되겠는데, erase 함수도 $O(N)$입니다. 지우는 시간을 획기적으로 단축할 방법이 없을까요?

 

Queue를 이용해 보면 어떨까요? front에서 사람들을 받고, 죽어있으면 버리고, 살아있으면 공격 후, Queue에 다시 집어넣는 식으로 말이죠!

#include<bits/stdc++.h>
#define health first
#define idx second

using namespace std;

queue<pair<int, int>> qu;

int power[202020], hp[202020];

int main () {
    int N; cin >> N;

    for (int i=0;i<N;i++) {
        cin >> power[i];
    }
    
    for (int i=0;i<N;i++) {
        cin >> hp[i];
    }

    for (int i=0;i<N;i++) {
        qu.emplace(hp[i], i);
    }

    int global_attack = 0;

    while(qu.size() != 1) {
        auto now = qu.front(); qu.pop();

        if (now.health <= global_attack) continue;

	//자기자신한테 피해를 입히지 않기 때문에, 자기자신 체력에 자신의 공격력을 더합니다.
        now.health += power[now.idx];
        global_attack += power[now.idx];

        qu.push(now);
    }

    cout << qu.front().idx + 1;
}

 

 

H. 의좋은 형제

결국 모든 논을 $N$번째로 모아야 합니다. $N-1$번째 논은 그냥 $N$번째로 뒤섞이면서 보내야 합니다. $1$번부터 $N-2$번까지의 논은 두 가지의 선택지가 존재하게 됩니다!

• $N$번째 논으로 바로 교차하면서 보내기
• $N-1$번째 논으로 보냈다가, $N$번째 논으로 보내기

이런 식으로 선택할 수 있다면, $N$번째 논에 원하는 곳에 무조건 보낼 수 있겠죠?

 

그럼 차이가 최대가 나게 하는 그리디 한 방법을 생각해 봅시다. 큰 것을 더욱더 크게 만들고, 작은 것을 덜 크게 만들면 계속 차이가 벌어지지 않을까요? 그런데, 형과 아우의 논 중에 뭘 크게 만들지 모르겠습니다.

 

둘 다 해보면 됩니다!

#include<bits/stdc++.h>

using namespace std;

int A[202020], B[202020];

int main () {
    int N; cin >> N;

    for (int i=0;i<N;i++) {
        cin >> A[i];
    }

    for (int i=0;i<N;i++) {
        cin >> B[i];
    }

    int mn = 0, mx = 0;

    for (int i=0;i<N-2;i++) {
        mn += min(A[i], B[i]);
        mx += max(A[i], B[i]);
    }

    A[N-1] += B[N-2];
    B[N-1] += A[N-2];

    int answer = max(abs((A[N-1] + mx) - (B[N-1] + mn)), abs((A[N-1] + mn) - (B[N-1] + mx)));

    cout << answer;
}

 

 

I. 식물 기르기

제가 만든 문제가 아니고, 제가 엄밀한 증명을 해보고, 이해한 문제가 아니어서 간략하게 밖에 설명하지 못하고 넘어갈 것 같습니다!

 

조금 관찰을 해보면 됩니다! 일단 수는 2의 거듭제곱꼴로 주어집니다. 즉, 서로가 서로에 대해 배수 약수 관계라는 것이죠. 

 

일단 간단하게 이렇게 생각해 볼 수 있습니다. 주기가 $K$인 꽃이 $K$개 있으면, $X$는 1이 더 필요하게 됩니다.

주기가 $K$인 꽃이, $N$개 있으면, $\big\lceil\frac{N}{K}\big\rceil$ 개의 X가 더 필요합니다.

 

이때, 주기가 $K^a$인 꽃이, $M$개 있으면, $\big\lceil\frac{N}{K} + \frac{M}{K^a} \big\rceil$ 으로 확장하여 적용 가능할까요?

가능합니다! 엄밀한 증명은 추후 정리하여 이해 후 올려보겠습니다!

 

J. 대전 도시철도 2호선

탐색 후, 계산만 해주면 되는 문제라고 생각하였습니다. 참가자 여러분들이 아직 트리 탐색에 대해, 익숙지 않아서 그냥 넘어가서 다른 문제를 푸시더라고요 ㅜ

 

조건들을 간략화해 봅시다!

$S \not= E$ 그리고, $S$와 $E$는 1호선 역에 포함되게 하면 안 됩니다.

$S$와 $E$를 잇는 단순경로는, 1호선 역을 하나 포함해야 합니다.

 

트리를 정말 간략하게 그려봅시다.

1번부터 N번을 잇는 단순 경로 위, 달려있는 정점의 갯수들

 

될 수 있는 순서쌍 $(S, E)$는 저 검은색 구역 안에 있는 각각 다른 집합에 속한 정점들의 개수입니다.

즉, 그림에서는 개수가 5개인 집합에 속한 정점과 개수가 3이나 7인 다른 집합에 속한 정점을 쌍으로 묶어야 2호선 조건을 완성하게 됩니다.

 

같은 집합에서 두 쌍을 2호선으로 만들면, 빨간색 1호선 역을 지나치지 않는다는 것을 볼 수 있습니다.

 

더 깔끔한 방법이 있지만, 경우의 수를 계산하는 데에 있어서, 이러한 방식을 사용해 보는 게 꽤 중요하기 때문에, 해당 코드를 첨부해 드립니다.

#include<bits/stdc++.h>

using namespace std;
typedef long long lint;

lint answer = 0;

int up[101010], siz[101010], N, way[101010];

vector<int> load[101010];


int dfs (int node, int prev) {
    siz[node] = 1;

    for (int next : load[node]) if (prev != next) {
            siz[node] += dfs(next, node);
        }

    return siz[node];
}

void dfs2 (int node, int prev) {
    for (int next : load[node]) if (prev != next) {
            up[next] = node;
            dfs2(next, node);
        }
}


int main () {
    ios_base::sync_with_stdio(0);cin.tie(0);
    cin >> N;

    for (int i=1;i<N;i++) {
        int u, v;
        cin >> u >> v;

        load[u].push_back(v);
        load[v].push_back(u);
    }

    dfs2(1, 0);

    int temp = N;
    while(temp != 0) {
        way[temp] = 1;
        temp = up[temp];
    }

    vector<lint> vc;

    for (int i=1;i<=N;i++) {
        if (!way[i]) continue;

        for (int next : load[i]) if (!way[next]) {
                vc.push_back(dfs(next, i));
        }
    }

    lint prefix = 0;

    for (lint e : vc) {
        answer += prefix * e;
        prefix += e;
    }

    cout << answer;
}

 

 

K. 멜로디

아직 작성중이에요ㅜ

 

 

L. 용감한 용사 수호

장비 $N$개 중에 $M$개를 착용 가능하다... 처음 보는 분들은 이게 도대체 어떻게 접근해야 할지 감도 안 잡힐 텐데요. 이런 류의 문제는 바로 DP (다이나믹 프로그래밍)으로 접근해야 합니다.

 

$dp[i][j]$ 를 공격력을 $i$로, 방어력을 $j$ 로 만들기 위한 최소한의 장비 개수라고 정의합시다.

이 디피테이블 위에서, 장비를 계속 추가하면서 최적으로 유지해 준다면, 우린 이 dp테이블 값을 통해, 실제로 우리가 도달가능한 공격력과 방어력 쌍을 모두 알아낼 수 있습니다.

 

그때, 잡을 수 있는 몬스터들을 구해주고,  가장 몬스터를 가장 많이 잡을 때의 몬스터 수를 정답으로 제출하면 되겠죠?

 

초기 점화식은 $dp[X][Y] = 0$입니다. $X$와 $Y$는 초기 수호의 공격력과 방어력이고, dp정의에 따르면, 이때 필요한 장비 수는 0개입니다.

 

장비의 공격력과 방어력을 각각 $x$ 와 $y$라고 합시다. 추가할 때, 냅색디피로 한번 쓱 훑어 줄 겁니다.

 

$$dp[i][j] = \min(\; dp[i][j], \; dp[i-x][j-y] + 1)$$

이때 범위에 유의해서 dp를 전이해야 합니다. 전이되는 값이 테이블에서 bound 된다고 하더라도, 맨 최상단에 넣어줄 필요가 있습니다. (299, 299) 상태에서 장비 (100,100)을 착용하면, (300, 300)으로 전이시켜야 한다는 뜻입니다.

 

자 그럼, 우리는 $dp[i][j]$ 값이 $M$보다 작거나 같은 값만 보면서, 잡을 수 있는 몬스터를 빠르게 세주어야 합니다!

 

이때 공격력이 $i$ 이하, 방어력이 $j$ 이하인 몬스터들의 수를 어떻게 빠르게 셀 수 있을까요?

쿼리를 날린다고 생각하면, 떠오르시는 게 있을 수도 있습니다. 2차원 누적합 쿼리를 응용해 봅시다!

#include<bits/stdc++.h>

using namespace std;

int N, M, X, Y;
int dp[303][303], mob[303][303];

int main () {
    cin.tie(0); ios_base::sync_with_stdio(0);

    cin >> N >> M >> X >> Y;

    fill_n(&dp[0][0], 303*303, 1e9);

    dp[X][Y] = 0;

    for (int i=0;i<N;i++) {
        int x, y; cin >> x >> y;

        for (int j=300;j>=0;j--) {
            for (int k=300;k>=0;k--) {
                int &t = dp[min(300, j+x)][min(300, k+y)];
                t = min(t, dp[j][k] + 1);
            }
        }
    }

    int K; cin >> K;

    for (int j=0;j<K;j++) {
        int p, q; cin >> p >> q;
        mob[p][q]++;
    }

    for (int i=0;i<=300;i++) {
        int temp = 0;
        for (int j=0;j<=300;j++) {
            temp += mob[i][j];
            mob[i][j] = temp + (i - 1 >= 0 ? (mob[i - 1][j]) : 0);
        }
    }

    int answer = 0;

    for (int i=0;i<=300;i++) {
        for (int j=0;j<=300;j++) {
            if (dp[i][j] <= M) {
                answer = max(answer, mob[i][j]);
            }
        }
    }

    cout << answer;
}

 

 

M. 계단 수열과 쿼리

전형적인 구조체 세그먼트 트리 문제입니다. 정확하게는 적당하게 최적화될 수 있게 구간들을 나누어 주고, 구간들에 대해, 구간 노드들의 합으로 새로운 구간을 만들 수 있을 정도의 정보를 저장합니다. 그게 문제 풀이의 핵심이 되겠습니다.

 

구간을 $\sqrt{N}$으로 나누어도 좋고, 세그먼트 트리 구조를 사용해, $2N$개의 구간으로 나누어도 됩니다. 저는 검수 당시, 더 빡빡한 시간제한을 시도해 보기 위해, Splay Tree를 사용하여, 필요한 구간을 그때그때 동적으로 만들어 보았습니다.

 

일반적인 구조체 세그먼트 트리 풀이를 해봅시다. $K$는 1부터 10까지의 정수입니다. 10가지 경우에 대해서만 다 해본다고 하더라도, 시간은 $O(10N \log N)$ 이어서 시간 내에 작동할 것입니다.

 

일단 세그먼트 트리의 노드에 대해 정의하여 봅시다.

struct node{
    int dp_left[11], dp_right[11], dp_max[11], dp_full[11];
};

 

• dp_left[i] : 구간의 맨 왼쪽 원소를 포함한 $\text{i}$-계단 수열의 최대 길이
• dp_right[i] : 구간의 맨 오른쪽 원소를 포함한 $\text{i}$-계단 수열의 최대 길이
• dp_full[i] : 구간 전체가 $\text{i}$-계단 수열이면 그 길이를 아니라면 0
• dp_max[i] : 구간의 $\text{i}$-계단 수열의 길이의 최댓값

이렇게 정의하면 두 개의 구간을 가지고 합칠 때, 새로운 구간을 만들 수 있습니다. 이때 양 구간에 이어지는 수 두 개를 인자로 받아 온다고 했을 때 다음과 같이 노드의 합 연산을 구현할 수 있습니다.

node sum (node left, int l, node right, int r) {
    node res;

    //이어지는 두 수의 차이
    int diff = abs(l - r);

    for (int i=1;i<=10;i++) {
        res.dp_max[i] = max(left.dp_max[i], right.dp_max[i]);
        res.dp_full[i] = left.dp_full[i] && right.dp_full[i] && diff == i ? left.dp_full[i] + right.dp_full[i] : 0;

        res.dp_left[i] = max(left.dp_left[i], diff == i && left.dp_full[i] ? left.dp_full[i] + right.dp_left[i] : 1);
        res.dp_right[i] = max(right.dp_right[i], diff == i && right.dp_full[i] ? left.dp_right[i] + right.dp_full[i] : 1);

        if (diff == i) { // 두 수열이 이어질 경우
            res.dp_max[i] = max(res.dp_max[i], left.dp_right[i] + right.dp_left[i]);
        }
    }

    return res;
}

 

최대한 적은 줄을 가지고 작성하기 위해, 삼항 연산자를 엄청 사용했습니다. 이제 노드에 대한 정의와 노드 합연산에 대한 정의가 끝났습니다.

 

이제는 쿼리 1번에 대응하는 Lazy 연산과, Push (Propagate) 연산을 만들어야 합니다. 정의가 완료된 구간에 대해, 모든 수에 $x$를 더하면, K-계단수열의 dp에는 아무런 변화가 없습니다. 따라서, Lazy 시켜놓고, 필요할 때만, 양쪽 수에 Lazy된 값을 push하고, 이미 탐색한 구간은 업데이트를 바로 해주면 됩니다. 간단합니다.

 

저는 검수를 위해, 스플레이 트리로 하드하게 밀었습니다.

 

스플레이 트리는 한 노드에 양쪽 구간이 달려있는 형태이기 때문에, 노드 3개의 합 연산에 대해, 2개의 노드에 대해 합연산을 2번 사용하여 해결했습니다.

#include<bits/stdc++.h>

using namespace std;


struct SPLAY {
    typedef long long lint;

    struct Node {
        Node *p = nullptr, *l = nullptr, * r = nullptr;
        int key, value, size = 1, dp[11];

        int lvalue = 0;
        int reLazy = 0, lazy = 0;

        int leftSize[11], rightSize[11];
        int leftStart, rightStart;


        Node (lint key, lint value) : key(key), value(value) {
            update();
        }

        Node sumation (Node *a, Node *b) {
            Node res(0, 0);
            res.size = a->size + b->size;
            res.leftStart = a->leftStart;
            res.rightStart = b->rightStart;

            for (int i=1;i<=10;i++) {
                res.dp[i] = max(a->dp[i], b->dp[i]);
            }

            for (int i=1;i<=10;i++) {
                bool connect = abs(a->rightStart - b->leftStart) == i;

                if (connect) {
                    res.dp[i] = max(res.dp[i], a->rightSize[i] + b->leftSize[i]);
                }

                res.leftSize[i] = a->leftSize[i];
                res.rightSize[i] = b->rightSize[i];

                res.leftSize[i] = a->leftSize[i];
                if (a->isFull(i) && connect) {
                    res.leftSize[i] = max(res.leftSize[i], a->size + b->leftSize[i]);
                }

                res.rightSize[i] = b->rightSize[i];
                if (b->isFull(i) && connect) {
                    res.rightSize[i] = max(res.rightSize[i], b->size + a->rightSize[i]);
                }
            }

            return res;
        }

        void put (Node a, Node *b) {
            b->size = a.size;
            b->leftStart = a.leftStart;
            b->rightStart = a.rightStart;

            for (int i=1;i<=10;i++) {
                b->dp[i] = a.dp[i];
                b->leftSize[i] = a.leftSize[i];
                b->rightSize[i] = a.rightSize[i];
            }
        }

        void update () {
            size = 1;

            fill(dp, dp+11, 1);
            fill(leftSize, leftSize+11, 1);
            fill(rightSize, rightSize+11, 1);

            leftStart = rightStart = value;

            if (l) {
                l->propagate();

                put(sumation(l, this), this);
            }

            if (r) {
                r->propagate();
                put(sumation(this, r), this);
            }
        }

        bool isFull (int k) {
            return size == leftSize[k];
        }

        void propagate () {
            if (reLazy) {
                swap(l, r);
                if (l) {
                    l->reLazy ^= 1;
                }

                if(r) {
                    r->reLazy ^= 1;
                }
                reLazy = 0;
            }

            if (!lazy) return;

            value += lvalue;
            leftStart += lvalue;
            rightStart += lvalue;

            if (l) {
                l->lazy = 1;
                l->lvalue += lvalue;
            }

            if (r) {
                r->lazy = 1;
                r->lvalue += lvalue;
            }

            lazy = lvalue = 0;
        }
    };

    Node *root;

    void rotate (Node* a) {
        Node* parent = a->p, *leaf;

        parent->propagate(); a->propagate();

        if (parent->l == a) {
            leaf = parent->l = a->r;
            a->r = parent;
        } else {
            leaf = parent->r = a->l;
            a->l = parent;
        }

        a->p = parent->p;
        parent->p = a;

        if (leaf) {
            leaf->p = parent;
        }

        if(a->p) {
            if (a->p->l == parent) {
                a->p->l = a;
            } else {
                a->p->r = a;
            }
        } else {
            root = a;
        }

        parent->update();
        a->update();
    }

    //노드를 스플레이 시킵니다. 기본적으로 전파와 업데이트를 한번 수행합니다.
    void splay (Node* a) {
        a->propagate();
        a->update();

        while(a->p) {
            if (a->p->p)
                rotate((a->p->p->l == a->p) == (a->p->l == a) ? a->p : a);
            rotate(a);
        }
    }
    //key 값과 value 값을 넣습니다. 있다면 value를 덮어씁니다.
    void push (lint key, lint value) {
        if (!root) {
            Node* a= new Node(key, value);
            root = a;
            return;
        }

        Node* now = root;

        while(1) {
            now->propagate();
            if (key < now->key) {
                if (now->l) now = now->l;
                else {
                    Node* a= new Node(key, value);

                    now->l = a; a->p = now;

                    splay(a);
                    return;
                }
            } else if (key > now->key) {
                if (now->r) now = now->r;
                else {
                    Node* a= new Node(key, value);

                    now->r = a;a->p = now;

                    splay(a);
                    return;
                }
            } else {
                splay(now);
                now->value = value;

                now->update();
                return;
            }
        }
    }

    //변수 order(1-based) 번째의 노드를 SPLAY 합니다. 구간 범위 아웃일 경우 False
    bool findKth (int order) {
        if (size() < order) return false;

        Node* now = root;
        splay(root);

        while(1) {
            now->propagate();
            if (now->l == nullptr && now->r == nullptr) break;

            if (now->l && now->r) {
                if (now->l->size + 1 == order) break;

                if (now->l->size < order) {
                    order -= now->l->size + 1;
                    now = now->r;
                } else {
                    now = now->l;
                }
            } else if (now->l) {
                if (now->l->size + 1 == order) break;

                now = now->l;
            } else {
                if (order == 1) break;

                now = now->r;
                order--;
            }
        }

        splay(now);
        return true;
    }

    //구간 [l, r]을 분리 해 냅니다. 리턴된 노드는 루트가 아님에 유의 하십시오.
    Node* segment (int l, int r) {
        if (r < l) return nullptr;

        r = min(r, size());
        l = max(l, 1);

        if (l == 1 && r == size()) {
            root->propagate();
            return root;
        } else if (l == 1) {
            findKth(r+1);
            root->l->propagate();

            return root->l;
        } else if (r == size()) {
            findKth(l-1);
            root->r->propagate();

            return root->r;
        } else {
            findKth(r+1);

            Node *rroot = root;
            root = rroot->l;

            rroot->l = 0;
            root->p = 0;

            findKth(l-1);

            Node *res = root->r; res->propagate();

            root->p = rroot; rroot->l = root;

            rroot->update();

            root = rroot;
            return res;
        }
    }

    //Splay Tree 안의 노드의 갯수를 리턴합니다.
    int size () {
        if (root) return root->size;
        return 0;
    }
};

SPLAY spl;


int main () {
    cin.tie(0);ios_base::sync_with_stdio(0);

    int N, Q; cin >> N >> Q;

    for (int i=0;i<N;i++) {
        int k; cin >> k;

        spl.push(i, k);
    }

    while(Q-->0) {
        int m, l, r, k;
        cin >> m >> l >> r >> k;

        if (m == 1) {
            auto *v = spl.segment(l, r);
            v->lazy = 1;
            v->lvalue = k;
            spl.splay(v);
        } else {
            auto *temp = spl.segment(l, r);
            cout << temp->dp[k] << '\n';
        }
    }
}

 

 

N. 카드 뒤집기 1

이 문제는 여러 풀이가 있는데요! 단조성을 이용하여, STACK에서 이분탐색을 하거나, 상위 자료구조 중 하나인 세그먼트 트리를 활용하는 방법  등이 있습니다.

 

그중에서 세그먼트 트리를 사용하여 푸는 방법에 대해서 말씀드리겠습니다.

 

만약, 카드 숫자가  $x$보다 큰 수인 $L$라고 해봅시다. 이 카드는 뒤집혀 있던 뒤집혀 있지 않던, $L$이 적힌  방향이 위로오게 바뀐다는 것을 알 수 있습니다. 반대로, 카드 숫자가 $x$보다 작은 수인 $S$인 카드들은, 무조건 뒤집힌다는 것을 관찰할 수 있습니다.

 

즉, 카드의 0이 아닌 부분에 적힌 숫자의 범위들에 따라, 카드를 뒤집거나 고정시키면 되는 것입니다.

 

이 연산을 느리게 전파하는 세그먼트 트리 (Lazy Segment Tree)를 사용하여, 구현하면 됩니다.

#include<bits/stdc++.h>

using namespace std;
const int MAX = 202020, T_MAX = 808080;
int N, tree[T_MAX], lazy_f[T_MAX], lazy_s[T_MAX];

void init (int n, int s, int e) {
    if (s == e) {
        tree[n] = 1;
        return;
    }

    int mid = s + e >> 1;
    init(n << 1, s, mid);
    init(n << 1 | 1, mid+1, e);
}

void push (int n, bool p) {
    if (lazy_s[n]) tree[n] = 1;
    tree[n] ^= lazy_f[n];

    if (p)  {
        if (lazy_s[n]) {
            lazy_s[n << 1] = lazy_f[n << 1] = 0;
            lazy_s[n << 1 | 1] = lazy_f[n << 1 | 1] = 0;
        }

        lazy_s[n << 1] |= lazy_s[n];
        lazy_s[n << 1 | 1] |= lazy_s[n];

        lazy_f[n << 1] ^= lazy_f[n];
        lazy_f[n << 1 | 1] ^= lazy_f[n];
    }

    lazy_s[n] = lazy_f[n] = 0;
}

void query_flip(int n, int s, int e, int l, int r) {
    if (r < s || e < l) return;
    push(n, l != r);


    if (s <= l && r <= e) {
        lazy_f[n] ^= 1;
        return;
    }

    int mid = l + r >>  1;

    query_flip(n << 1, s, e, l, mid);
    query_flip(n << 1 | 1, s, e, mid+1,  r);
}

void query_set (int n, int s, int e, int l, int r) {
    push(n, l != r);
    if (r < s || e < l) return;


    if (s <= l && r <= e) {
        lazy_s[n] = 1;
        return;
    }

    int mid = l + r >>  1;

    query_set(n << 1, s, e, l, mid);
    query_set(n << 1 | 1, s, e, mid+1,  r);
}

int finder (int n, int s, int e,  int idx) {
    push(n, s != e);

    if (s == e) return tree[n];

    int mid = s + e >> 1;

    if (idx <= mid) return finder(n << 1, s, mid, idx);
    else return finder(n << 1 |  1, mid+1, e, idx);
}


int main () {
    cin.tie(0);ios_base::sync_with_stdio(0);
    
    cin >> N;
    init(1, 1, N);

    for (int i=0;i<N;i++) {
        int x; cin >> x;

        int state = finder(1, 1,  N, x) ? x : 0;
        cout << state <<  ' ';

        if (state == 0) continue;

        query_flip(1, 1, x-1, 1, N);
        query_set(1, x+1, N, 1, N);
    }
}

 

 

O. 카드 뒤집기 2

문제 N번의 관찰을 필요로 하는 문제입니다. N번에서의, 범위에 따라 카드가 뒤집히고 안 뒤집히는 것을  응용해야 합니다.

$\text{query}(i, x)$를 $i$번째 인덱스보다 큰 인덱스의 카드에 숫자 $x$로 뒤집기를 시도한다고 정의해보겠습니다.

 

우리는 앞써, 쿼리에 사용된 $(i, x)$ 쌍들을 잘 보관하고 있고, 이 값들을 활용하여, 새로운 인덱스에서의 카드의  앞장, 뒷장을 빠른 시간 안에 결정할 수 있다면, 문제를 풀 수 있을 것입니다.

 

제일 중요한 관찰에 대해 서술하겠습니다. 현재 결정하려는 카드의 숫자의 앞면 뒷면이 각각, $S$, $L$이라고 하겠습니다.

어떠한 쿼리가 어떻게 오든, 범위 $(S, L]$ 사이의 값 $x$가  쿼리로 온 시점에는 윗면이 $L$로 고정됩니다. 즉, 그 이전까지의 쿼리는 필요가 없다고 해석할 수 있습니다.

 

그럼, 쿼리의 쌍중, $( S ＜ x  \leq L)$인, $x$중에 가장 큰 $i$쿼리부터 카드 뒤집기에 영향이 주는 쿼리의 개수를 세서 결정하면 됩니다.

 

이 과정은, RMQ를 지원하는 세그먼트 트리와, Persistance Segment tree, Sqrt Decompostion 또는 MergeSort Tree로 해결할 수 있습니다.

 

RMQ를 지원하는 세그먼트 트리를 통해, $[S+1, L]$ 범위 사이의  가장 큰 쿼리 인덱스를 찾고, 그 쿼리 인덱스부터 마지막 쿼리까지, L보다 큰 $x$가 쿼리로 몇 개 있었는지 세주면 됩니다.

#include<bits/stdc++.h>

using namespace std;

// Persistance Segment Tree : 1부터 N까지의 수를 관리합니다.
class PSEG {
public:
    class node {
    public:
        int sum = 0;
        node *l, *r;

        node() : sum(0) {}
    };

    vector<node*> nodes;

    PSEG (int N) : N(N) {
        nodes.push_back(init(1, N));
    }

    PSEG (vector<int> &vec) : N(202020) {
        nodes.push_back(init(1, N));

        for (int e : vec) {
            nodes.push_back(update(nodes.back(), 1, N, e, 1));
        }
    }

private:
    int N;

    node* init (int l, int r) {
        if (l == r) {
            return new node();
        }

        node *now = new node();

        int mid = l + r >> 1;
        now->l = init(l, mid);
        now->r = init(mid+1, r);

        return now;
    }

    int query (node* up, node* down, int s, int e, int l, int r) {
        if (r < s || e < l) return 0;

        if (s <= l && r <= e) {
            return up->sum - down->sum;
        }

        int mid = l + r >> 1;

        return query(up->l, down->l, s, e, l, mid)
               + query(up->r, down->r, s, e, mid+1, r);
    }
public :
    //l, r 인수는 1-based 입니다.
    int query (int l, int r, int k) {
        return query(nodes[r], nodes[l-1], k+1, N, 1, N);
    }

    // now로 기록된 매개체를 통해 업데이트된 새로운 트리의 구조체를 리턴합니다.
    node* update (node *now, int l, int r, int idx, int d) {
        if (r < idx  || idx < l) return now;

        if (l == r && l == idx) {
            node *temp = new node();
            temp->sum = now->sum + d;
            return temp;
        }

        int mid = l + r >> 1;

        node *temp = new node();
        temp->l = update(now->l, l, mid, idx, d);
        temp->r = update(now->r, mid+1, r, idx, d);

        temp->sum = temp->l->sum + temp->r->sum;

        return temp;
    }
};

PSEG psg(404040);

int A[202020], B[202020], tree[450000*4];

void init (int n, int s, int e) {
    if (s == e) {
        tree[n] = -1;
        return;
    }

    int mid = s + e >> 1;
    init(n << 1, s, mid); init(n << 1 | 1, mid+1, e);

    tree[n] = max(tree[n << 1], tree[n << 1 | 1]);
}

void update (int n, int s, int e, int idx, int value) {
    if (s == e) {
        tree[n] = value;
        return;
    }

    int mid = s + e >> 1;

    if (idx <= mid) update(n << 1, s, mid, idx, value);
    else update(n << 1 | 1, mid+1, e, idx, value);

    tree[n] = max(tree[n << 1], tree[n << 1 | 1]);
}

int query (int n, int s, int e, int l, int r) {
    if (r < s || e < l || r < l) return -1;

    if (s <=l && r <= e) return tree[n];

    int mid = l + r >> 1;

    return max(query(n << 1, s, e, l, mid), query(n << 1 | 1, s, e, mid+1, r));
}

int main () {
    cin.tie(0);ios_base::sync_with_stdio(0);
    int N; cin >> N;

    for (int i=0;i<N;i++) cin >> A[i];
    for (int i=0;i<N;i++) cin >> B[i];

    init(1, 1, 404040);

    for (int i=0;i<N;i++) {
        int mn = min(A[i], B[i]);
        int mx = max(A[i], B[i]);

        // [mn+1, mx] -> mx [mx+1, INF] -> turn

        int idx = query(1, mn+1, mx, 1, 404040);

        if (idx == -1) idx = 1;
        else {
            A[i] = mx; B[i] = mn;
        }

        //[idx, i] 까지

        int turned = psg.query(idx, i, mx);

        if (turned & 1) swap(A[i], B[i]);

        cout << A[i] << ' ';

        psg.nodes.push_back(psg.update(psg.nodes.back(), 1, 404040, A[i], 1));
        update(1, 1, 404040, A[i], i+1);
    }
}