Codeforces Round #766 A부터 C까지 업솔빙

Codeforces Round #766 A부터 C까지 업솔빙

B번 문제가 게임이론? 이걸 어떻게 알아 ㅋㅋㅋㅋㅋㅋㅋㅋㅋ 근데 막상 풀이 보면 납득이 가는 이유라서 정말 어이없는 문제. 이해가 정말 잘되서 놀랐다. C번 문제는 정수론 관련된 문제인데 알고리즘을 위한 정수론이 참 애매한것 같다. 정수론이 흔들리면 알고리즘에서 약점이 되는데, 그렇다고 막상 정수론을 공부하자고 하니 투머치인것 같고... 그냥 계속 문제 풀자.

A. Not Shading (*800)

접기/펼치기

문제 설명
$n \times m$ 크기의 격자판이 있다. 몇개 격자에는 검은색으로 칠해져있고, 나머지는 흰색으로 칠해져 있다.

한번의 연산으로 검은 격자중 하나를 선택해서 다음 연산을 한번 실행한다.

• 해당 격자를 포함한 모든 행을 검은색으로 칠한다.
• 해당 격자를 포함한 모든 열을 검은색으로 칠한다.

두 정수 $r$과 $c$가 있을 때, $(r, c)$인 곳을 검은색으로 칠하기 위한 최소 연산횟수를 구하라.

문제 해설
자명하게 일단 $(r, c)$가 검은색이면 연산이 필요 없다. 마찬가지로 모든 칸이 흰색이면 연산 자체를 수행할 수 없기 때문에 불가능하다.

$r$행 혹은 $c$열 둘중 하나에 검은색 칸이 하나라도 있으면 그 칸을 선택해서 연산을 1번 실행하면 된다. $r$행, $c$열 모두 검은색 칸이 없다면 임의의 한 행을 선택한 다음 그 행을 다 칠하과 $c$열을 선택해서 그 열을 다 칠하면 되므로 2번 실행하면되고, 이 4가지 경우뿐이다.

정답 코드

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int t; cin >> t;
    while(t--){
        int n, m, r, c; cin >> n >> m >> r >> c;
        char a[n + 1][m + 1];
        bool flag = true;
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= m; j++){
                cin >> a[i][j];
                if(a[i][j] == 'B') flag = false;
            }
        }

        if(flag){
            cout << -1 << "\n";
            continue;
        }

        if(a[r][c] == 'B') cout << 0;
        else{
            for(int i = 1; i <= n; i++){
                if(a[i][c] == 'B') flag = true;
            }
            for(int i = 1; i <= m; i++){
                if(a[r][i] == 'B') flag = true;
            }
            cout << (flag ? 1 : 2);
        }
        cout << "\n";
    }
    return 0;
}

B. Not Sitting (*1300)

접기/펼치기

문제 설명
학생들이 앉는 자리는 $n \times m$ 크기의 격자로 이루어져 있으며 두 자리 $(a, b)$와 $(c, d)$의 거리는 $|a - c| + |b - d|$로 정의한다.

반장인 지현이는 정확히 $k$개 좌석을 핑크색으로 칠할 수 있으며, 다음 과정이 순서대로 일어난다.

1. 지현이는 정확히 $k$개 좌석을 선택해서 핑크색으로 칠한다.
2. 지현이가 좌석을 칠한 이후에, 민호는 자기가 앉을 자리를 선택한다. 민호는 핑크색으로 칠한 자리는 앉을 수 없다.
3. 민호가 좌석을 선택한 이후에, 지현이가 앉을 자리를 선택한다. 지현이는 아무자리나 앉을 수 있지만 민호가 앉은 자리는 선택할 수 없다.

민호는 지현이랑 최대한 가까이 앉고 싶고, 지현이는 최대한 민호와 먼거리에 앉고 싶어한다.
$k = 0, 1, ..., n \cdot m - 1$ 일때, 만약 지현이가 $k$개 좌석을 칠할때, 지현이와 민호가 앉을 수 있는 최적의 자리사이 거리를 구해야 한다.

문제 해설
이런 유형의 문제를 게임이론 문제라고 하는데, 솔직히 어떻게 풀어야할지 감이 안잡혔다.
문제를 읽고 나면 결국 민호는 최대한 가운데에 앉아야 하고, 지현이는 격자의 네 귀퉁이에 앉아야 최적이라는 사실을 알 수 있다고 해설에서 나왔다.
민호는 결국 모든 자리를 앉아야 하기 때문에 모든 자리을 확인해보면서 해당 자리와 네 귀퉁이 사이 거리중 가장 긴 값을 배열에 넣은 이후, 오름차순으로 정렬해서 출력하면 답이 된다.

이 문제의 핵심은 지현이는 반드시 귀퉁이에 앉아야 한다는 점과 민호는 결국 모든 자리를 앉아야 한다는 점, 마지막으로 지현이와 민호 사이의 거리를 최대화 해야한다는 점이다.

정답 코드

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int t; cin >> t;
    while(t--){
        int n, m; cin >> n >> m;
        int x[4] = {0, n - 1, 0, n - 1}, y[4] = {0, 0, m - 1, m - 1};
        vector<int> v;
        for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++){
                int ans = 0;
                for(int k = 0; k < 4; k++){
                    ans = max(ans, abs(x[k] - i) + abs(y[k] - j));
                }
                v.push_back(ans);
            }
        }
        sort(v.begin(), v.end());
        for(auto x : v) cout << x << " ";
        cout << "\n";
    }
    return 0;
}

C. Not Assigning (*1400)

접기/펼치기

문제 설명
$1$부터 $n$까지 번호가 부여된 $n$개 정점으로 이루어진 트리가 주어진다. 그리고 간선은 $1$부터 $n - 1$까지 번호가 부여된다. 우리는 소수 트리를 만들어야 한다.

소수 트리 란 한개 혹은 2개 간선으로 이루어진 모든 경로의 가중치가 소수여야 한다. 한 경로의 가중치는 해당 경로를 지나는 간선의 가중치 총 합이다.

소수 트리를 만들기 위해서 필요한 가중치를 구해라. 만약 그런 가중치가 없다면 -1을 출력하라.

문제 해설
먼저 소수는 2를 제외하고 모두 홀수라는 사실을 먼저 알고 가야한다. 그리고 두 수를 더해서 홀수를 만들기 위해서 반드시 짝수 + 홀수 조합이어야 하기 때문에 반드시 2가 필요하다는 것을 알 수 있다.

또한 1개 혹은 2개 간선으로 이루어진 모든 경로를 확인해야 하는데, 만약 한 정점에 간선이 3개 이상이 붙어있다면 어떻게 해야할까? 한 정점에 간선이 3개 이상 있다면 이 정점을 통하는 모든 경로가 절대 홀수가 될 수 없다. 따라서 소수가 될 수 없다.

즉 먼저 해당 트리의 모든 정점을 확인할 때, 정점의 차수가 3이상이 있으면 그 트리는 소수 트리를 만들 수 없기 때문에 -1을 출력한다. 나머지 경우는 반드시 만들 수 있으며 일직선 형태가 된다.

그러면 차수가 1인 지점 한곳을 아무나 잡고 그 지점 부터 bfs, dfs를 해서 각 간선이 가지고 있는 번호에 2와 3을 번갈아가면서 지정하면 답이 된다.

정답 코드

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int t; cin >> t;
    while(t--){
        int n; cin >> n;
        vector<pair<int, int>> g[n + 1];
        vector<int> visit(n + 1), ans(n - 1);
        for(int i = 0; i < n - 1; i++){
            int u, v; cin >> u >> v;
            g[u].push_back({v, i});
            g[v].push_back({u, i});
        }

        bool flag = false;
        for(int i = 1; i <= n; i++){
            if(g[i].size() > 2){
                flag = true;
                break;
            }
        }
        if(flag){
            cout << -1 << "\n";
            continue;
        }
        queue<int> q;
        for(int i = 1; i <= n; i++){
            if(g[i].size() == 1){
                q.push(i);
                break;
            }
        }

        while(q.size()){
            int node = q.front(); q.pop();
            visit[node] = true;
            for(auto [x, y] : g[node]){
                if(visit[x]) continue;
                ans[y] = (flag ? 3 : 2);
                flag = !flag;
                q.push(x);
            }
        }
        for(auto x : ans) cout << x << " ";
        cout << "\n";
    }
    return 0;
}