[코드포스] Codeforces Round #771 (Div. 2) 풀이

https://codeforces.com/contest/1638

Dashboard - Codeforces Round #771 (Div. 2) - Codeforces

 

A. Reverse

풀이

• 오름차순으로 되어있을 때 사전 순으로 맨 앞이다.
• 오름차순 정렬된 상태와 처음으로 같지 않을 때 그 위치에 있어야 할 수가 그 위치에 오도록 reverse 하지 않으면 그렇게 한 것보다 사전 순으로 뒤에 있다.
• 따라서 그 위치에 오도록 reverse 하는게 사전 순으로 맨 앞이다.

코드

• 시간복잡도: $O(N)$

#include <bits/stdc++.h>
 
using namespace std;
 
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
 
    int TC; cin >> TC;
    while (TC--) {
        int N;
        cin >> N;
 
        vector<int> a(N);
        for (auto& e: a) {
            cin >> e;
        }
        vector<int> tmp(a);
        sort(all(tmp));
 
        for (int i = 0; i < N; ++i) {
            if (a[i] != i + 1) {
                auto it = find(a.begin() + i + 1, a.end(), i + 1);
                reverse(a.begin() + i, it + 1);
                break;
            }
        }
        for (auto& e: a) {
            cout << e << ' ';
        }
        cout << '\n';
    }
}

 

 

B. Odd Swap Sort

풀이

• 홀수, 짝수 사이는 자유롭게 스왑가능하다.
• 홀수, 홀수 이거나 짝수, 짝수 이면 스왑불가능하다.
• 따라서 operation 후 홀수들간의 위치관계 와 짝수들간의 위치관계는 각각 유지된다.
• 짝수, 홀수 들이 각각 정렬된 상태이면 전체를 정렬할 수 있다.

코드

• 시간복잡도: $O(N)$

#include <bits/stdc++.h>
 
using namespace std;
 
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
 
    int TC; cin >> TC;
    while (TC--) {
        int N;
        cin >> N;
        vector<long long> odd, even;
 
        for (int i = 0; i < N; ++i) {
            int num;
            cin >> num;
            if (num & 1) {
                odd.push_back(num);
            } else {
                even.push_back(num);
            }
        }
 
        if (is_sorted(all(odd)) && is_sorted(all(even))) {
            cout << "Yes\n";
        } else{
            cout << "No\n";
        }
    }
}

 

 

C. Inversion Graph

풀이

• Disjoint set 자료구조에서 각 셋의 최댓값을 루트로 한다.
• 배열 원소 차례로 순회하면서 이전 set 들의 최댓값들 중 지금 원소보다 큰 값이 있으면 union 한다.

코드

• 시간복잡도: 아마 $O(NlogN)$

※ 스택으로 연결된 그룹의 min, max 관리하면 $O(N)$ 으로 처리 가능

#include <bits/stdc++.h>
 
using namespace std;
 
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
 
 
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int TC; cin >> TC;
    while (TC--) {
        int N;
        cin >> N;
        vector<int> a(N);
        for (auto& e: a) {
            cin >> e;
        }
 
        vector<int> p(N + 1, -1);
        function<int(int)> myFind = [&](int n) {
            if (p[n] == -1) return n;
            return p[n] = myFind(p[n]);
        };
        set<int> s;
        auto myUnion = [&](int n1, int n2) {
            int p1 = myFind(n1);
            int p2 = myFind(n2);
 
            if (p1 == p2) return;
            if (p1 > p2) swap(p1, p2);
            p[p1] = p2;
            s.erase(p1);
        };
 
        int answer = N;
        s.insert(a[0]);
        for (int i = 1; i < N; ++i) {
            auto it = s.upper_bound(a[i]);
            if (it != s.end()) {
                while (it != s.end()) {
                    myUnion(a[i], *it);
                    --answer;
                    it = s.upper_bound(myFind(a[i]));
                }
            } else {
                s.insert(a[i]);
            }
        }
        cout << answer << '\n';
    }
}

 

D. Big Brush

풀이

• 색칠순서를 역순으로 구성한다.
• 처음에는 4칸이 모두 같은색인 곳을 칠한다.
• 이전에 칠한곳은 지금칠할 곳을 덮어쓰므로 어떤색이어도 상관없다.
• 이전에 칠한곳 근처에서 4칸 중 이전에 칠한곳을 제외한 칸들이 모두 같은색이면 칠한다.

코드

• BFS
• 시간복잡도: $O(NM)$

#include <bits/stdc++.h>
 
using namespace std;
 
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
 
    int N, M;
    cin >> N >> M;
 
    vector<vector<int> > a(N, vector<int> (M));
    vector<vector<int> > b(N, vector<int> (M, 0));
 
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < M; ++j) {
            cin >> a[i][j];
        }
    }
 
    queue<tuple<int, int, int> > q;
    auto check = [&](int i, int j) {
        if (i < 0 || i >= N - 1 || j < 0 || j >= M - 1) return 0;
        set<int> color;
        for (int ii = 0; ii < 2; ++ii) {
            for (int jj = 0; jj < 2; ++jj) {
                if (!b[i + ii][j + jj]) {
                    color.insert(a[i + ii][j + jj]);
                }
            }
        }
 
        if (color.size() == 1) {
            return *color.begin();
        } else {
            return 0;
        }
    };
 
    vector<vector<int> > visited(N - 1, vector<int> (M - 1, false));
    for (int i = 0; i < N - 1; ++i) {
        for (int j = 0; j < M - 1; ++j) {
            auto c = check(i, j);
            if (c) {
                q.push({i, j, c});
                visited[i][j] = true;
            }
        }
    }
 
    vector<tuple<int, int, int> > answer;
    int dr[8] = {-1, -1, -1, 0, 0, 1, 1, 1};
    int dc[8] = {-1, 0, 1, -1, 1, -1, 0, 1};
    while (q.size()) {
        int cnt = q.size();
            auto [i, j, c] = q.front();
            q.pop();
            answer.push_back({i, j, c});
            b[i][j] = b[i + 1][j] = b[i][j + 1] = b[i + 1][j + 1] = true;
            for (int dir = 0; dir < 8; ++dir) {
                int ni = i + dr[dir];
                int nj = j + dc[dir];
                if (ni < 0 || ni >= N - 1 || nj < 0 || nj >= M - 1 || visited[ni][nj]) continue;
                auto nc = check(ni, nj);
                if (nc) {
                    q.push({ni, nj, nc});
                    visited[ni][nj] = true;
                }
            }
    }
 
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < M; ++j) {
            if (!b[i][j]) {
                cout << "-1\n";
                return 0;
            }
        }
    }
 
    reverse(all(answer));
    cout << answer.size() << '\n';
    for (auto [i, j, c]: answer) {
        cout << i + 1 << ' ' << j + 1 << ' ' << c << '\n';
    }
}