AtCoder Beginner Contest 226 A부터 E까지 업솔빙

AtCoder Beginner Contest 226 A부터 E까지 업솔빙

D번까지 다 푼셋이다. 엣코더에서는 한 70%확률로 800까지 난이도 문제를 풀 수 있고, 그 위에 있는 난이도 문제는 50%확률로 풀 수 있는 것 같다. 티어가 오를 수 있다는 가능성이기 때문에 엣코더를 꾸준히 도전하고 싶다. 이번 대회에서 배운 내용은 무방향 그래프의 사이클 판독 특수한 경우? 라서 한번 경험해보면 좋을 것 같은 문제였다.

문제 옆에 붙어있는 난이도는 Atcoder Problems 에서 추정한 것으로 작성했다는 것을 미리 알린다.

A - Round decimals (*14)

접기/펼치기

문제 설명
최대 소숫점 이하 3자리까지 표현할 수 있는 실수 $X$가 주어진다.
해당 $X$와 가장 가까운 정수를 출력하라.

문제 해설
C++에는 round함수가 있다.

정답 코드

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

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);
    double x; cin >> x;
    cout << round(x) << "\n";
    return 0;
}

B - Counting Arrays (*192)

접기/펼치기

문제 설명
$1$ 부터 $N$까지 번호가 부여되어 있는 수열 $N$개가 주어진다.
수열 $i$는 길이가 $L_i$이고, 그 수열의 $j$번째 원소는 $(1 \le j \le L_i)$ 는 $a_{i, j}$ 이다.

수열 $i$와 수열 $j$는 모든 $k(1 \le k \le L_i)$ 에 대해서 $L_i = L_j$이고, $a_{i, k} = a_{j, k}$ 일때 같다고 한다.

수열 $1$부터 $N$까지 중에서 서로 다른 수열의 개수는 몇개일까?

문제 해설
C++의 SET은 중복을 허용하지 않는 자료구조인데, 무려 vector그 자체도 중복을 처리할 수 있다.

정답 코드

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

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);
    int n; cin >> n;
    set<vector<int>> s;
    while(n--){
        int l; cin >> l;
        vector<int> tmp(l);
        for(int i = 0; i < l; i++) cin >> tmp[i];
        s.insert(tmp);
    }
    cout << s.size();
    return 0;
}

C - Martial artist (*539)

접기/펼치기

문제 설명
철수는 마샬아츠 안무가이다. 철수가 배워야하는 안무는 총 $N$개 이고, 안무 $i$를 연습하기 위해서 $T_i$분이 필요하다. 추가적으로 연습을 시작하기 위해서는 안무 $A_{i, 1}, A_{i, 2}, ..., A_{i, K_i}$를 미리 배워놓아야 한다. 여기서 각 $1 \le j \le K_i$ 에 대해서 $A_{i, j} < i$를 반드시 만족한다.

철수는 시간 $0$분에 아무 안무도 알고있지 않다. 철수는 동시에 한개보다 더 많은 안무를 연습할 수 없으며, 이미 연습 시작한 안무는 도중에 멈출 수 없다. 철수가 안무 $N$을 배우기 위해서 필요한 최소 시간을 구하라.

문제 해설
결국 안무 $N$을 배우기 위해서 그 전에 있는 안무를 반드시 배워야 한다. 그런데 문제 조건에서 $i$번째 안무를 배우기 위해서는 $i$보다 작은 번호의 안무를 배워야 한다는 조건이 있기 때문에 문제가 쉬워진다.

그냥 $N$부터 $1$까지 순회하면서 $N$을 배우기 위해서 필요한 안무를 표시하고, $N - 1$번째 안무를 확인할때, 필요하다고 표시하지 않는 경우 그 안무를 패스하는 방식으로 그리디하게 탐색하면 쉽다. 이게 가능한 이유는 위에서 언급한 조건인 $i$보다 작은 안무만 필요하다는 점이 크다.

정답 코드

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

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);
    int n; cin >> n;
    vector<int> g[n + 1], t(n + 1), need(n + 1);
    for(int i = 1; i <= n; i++){
        cin >> t[i];
        int k; cin >> k;
        while(k--){
            int num; cin >> num;
            g[i].push_back(num);
        }
    }

    long long ans = 0;
    need[n] = 1;
    for(int i = n; i > 0; i--){
        if(!need[i]) continue;
        ans += t[i];
        for(auto x : g[i]) need[x] = 1;
    }
    cout << ans;
    return 0;
}

D - Teleportation (*706)

접기/펼치기

문제 설명
앳코더 공화국에는 직교 좌표계 판이 존재한다.
이 판에는 $N$개 마을이 있으며, $i$번째 마을은 $(x_i, y_i)$에 위치한다. 그리고 서로 다른 마을은 같은 좌표에 위치해 있지 않다.

이 나라에는 순간이동 마법이 있는데, 이 마법은 한쌍의 정수 $(a, b)$로 이루어져 있고, 이 $(a, b)$를 발동하면 좌표 $(x, y)$에서 $(x + a, y + b)$로 이동한다.

철수는 아무 마법 $(a, b)$를 모두 배울 수 있는 대마법사다. 철수가 배울 수 있는 마법은 무제한이다.
철수가 모든 마을을 여행하기 위해서 선택해야할 마법의 최소 개수는 몇개일까?

• 단. 해당 마법을 선택하면 한 마을을 도착할 때까지 해당 마법만을 사용해야 한다.

문제 해설
c번 문제보다 개인적으로 쉬운 문제였다. 이 문제의 핵심은 가능한 모든 좌표들 중에서 상수배로 표현되는 중복되는 좌표를 어떻게 제거하는지이다. 중복되는 요소를 제거할 수 있는 자료구조는 set이기 때문에 set을 사용하는데, 상수배를 어떻게 제거할까? 답은 두 정수의 최대 공약수로 나눠준다면 쉽게 상수배를 없앨 수가 있다. 간단한 정수론 지식이 필요한 문제였다.

c++에서는 유클리드 알고리즘을 사용해서 쉽게 최대공약수를 구할 수 있는 gcd함수가 내장되어있다.

정답 코드

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

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);
    int n; cin >> n;
    int x[n], y[n];
    for(int i = 0; i < n; i++) cin >> x[i] >> y[i];
    set<pair<int, int>> s;
    for(int i = 0; i < n; i++){
        for(int j = i + 1; j < n; j++){
            int dx = x[j] - x[i], dy = y[j] - y[i];
            int dv = gcd(dx, dy);
            s.insert({dx / dv, dy / dv});
            s.insert({-dx / dv, -dy / dv});
        }
    }
    cout << s.size();
    return 0;
}

E - Just one (*1327)

접기/펼치기

문제 설명
$N$개 정점과 $M$개 간선으로 이루어져 있는 무방향 그래프가 주어진다.
정점은 $1$부터 $N$까지, 간선은 $1$부터 $M$까지 번호가 붙여있고 간선 $i$는 정점 $A_i$와 $B_i$를 연결한다. 이 그래프는 자기 자신을 향한 루프도 없으며, 멀티 간선도 존재하지 않는다.

이 그래프에서 모든 정점을 있는 방향 간선을 그리는 방법이 총 $2^M$가지 존재한다. 우리는 한 정점에서 다른 정점을 향한 방향 간선이 단 한개가 되도록 그래프 간선을 그리고 싶다. 이런 조건을 만족하는 방법이 총 몇개 있을까? 답이 크므로 $998244353$ 으로 나눈 나머지 값을 출력하라.

문제 해설
문제를 이해조차 못했다. 문제를 30분 동안 읽으면서 깨달은 점은 사이클이 있어야 할 거 같은데, 이 싸이클인 경우를 어떻게 판독하지? 랑 싸이클이 아니여도 정점이 하나씩 붙어있으면 될거 같은데 확신을 못하겠네.. 라는 생각이었다.

일단 첫번째 생각은 문제에서 의도한게 맞았다. 사이클이 있어야지 한방향으로 방향 간선을 그릴 수 있기 때문이다. 그리고 사이클 1개당 2개의 경우가 나오기 때문에 2의 사이클 개수승 만큼이 답이다.

그러면 이 사이클이 있다는 것을 어떻게 판별할까? 이 문제에서는 기본적인 단순한 사이클인 경우부터 시작한다. 정점이 4개인 사이클은 정점이 총 4개 있고, 해당 정점의 DEGREE를 모두 더하면 2가 4개 있기 때문에 8이다. 즉 정점의 수를 $x$라고 하고 해당 정점의 degree의 합을 $y$라고 하면 $2 \times x = y$라는 식이 완성된다. dfs를 사용해서 방문하지 않은 모든 정점에 대해서 탐색을 수행하고 위 조건을 만족하면 2를 곱하고 아니면 0으로 바꿔버린다. 왜냐하면 사이클이 하나라도 아닌경우에는 문제의 요구사항을 전혀 만족할 수 없기 때문이다.

이제 2번째 생각으로 넘어가보자. 저 사이클에 추가적으로 뭔가 붙어도 될까? 답은 여러개 정점과 그 정점을 잇는 단 한개씩의 간선이 있으면 가능하다. 왜냐하면 해당 간선에서 다른 간선으로 나가는 방향이 1가지이면 되는거지 한 정점으로 들어오는 간선의 수는 여러개여도 상관 없기 때문이다. 즉 정점과 그 정점을 잇는 간선이 단 하나라면 사이클 1개랑 있는 경우랑 똑같이 때문에 상관 없고, 심지어 이 경우를 계산해보면 추가로 들어오는 정점에 degree가 1이지만 그 정점에서 다른 정점으로 이을때 연결되는 정점이 degree가 3이 되기 때문에 결국 위 x와 y식은 그대로 맞게 된다.

정답 코드

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

using ll = long long;
const int mod = 998244353;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);
    int n, m; cin >> n >> m;
    vector<int> g[n + 1], visited(n + 1);
    while(m--){
        int u, v; cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }

    ll ans = 1;
    for(int i = 1; i <= n; i++){
        if(visited[i]) continue;
        int x = 0, y = 0;
        function<void(int)> dfs = [&](int node){
            visited[node] = 1;
            x++;
            y += g[node].size();
            for(auto i : g[node]){
                if(!visited[i]) dfs(i);
            }
        };
        dfs(i);
        if(x * 2 == y) ans = (ans * 2) % mod;
        else ans = 0;
    }
    cout << ans;
    return 0;
}