AtCoder Beginner Contest 214 A부터 D까지 업솔빙

AtCoder Beginner Contest 214 A부터 D까지 업솔빙

이제 Atcoder에서 마지막으로 푼 문제에다 +1개 문제까지 해서 업솔빙을 하려고 한다. 우연히 *1500문제를 풀어봤는데, 내가 풀 수 있을 것 같은 문제도 있었던 것 같아서 계속 답지 보면서 이해하려고 노력하고 있다. 계속 *800, *1000 문제만 풀면 계속 그 수준이지만 더 높은 단계 문제를 이해하고 풀 수 있다면 당연하게도 레이팅이 올라갈 것같다.
이번 대회에서 배운 것은

1. DSU(분리집합)과 최단거리 결합한 응용문제
2. DSU의 활용

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

A - New Generation ABC (*4)

접기/펼치기

문제 설명
지금은 214번째 atcoder beginner contest(ABC)가 개최중이다.

한 ABC대회에는 다음과 같은 문제 개수를 가지고 있다.

• $1$번째 부터 $125$번째 ABC는 각각 4개 문제를 가지고 있다.
• $126$번째 부터 $211$번째 ABC는 각각 6개 문제를 가지고 있다.
• $212$번째 부터 $214$번째 ABC는 각각 8개 문제를 가지고 있다.

$N$번째 ABC가 가지고 있는 문제 수를 구하라.

문제 해설
조건문 3개 사용하면 됩니다. $N \le 214$이므로 따로 예외처리 안해도 됩니다.

정답 코드

#include <iostream>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int n; cin >> n;
    if(1 <= n && n <= 125) cout << 4;
    else if(126 <= n && n <= 211) cout << 6;
    else cout << 8;
    cout << "\n";
    return 0;
}

B - How many? (*53)

접기/펼치기

문제 설명
$a + b + c \le S$와 $a \times b \times c \le T$를 만족하는 음이 아닌 정수 세 쌍 $(a, b, c)$는 몇개일까?

문제 해설
완전탐색의 기초이자 완전 기초인 문제이다. 알고리즘 문제를 풀 때는 문제 조건을 보면 대충 출제자가 어떤 의도를 가지고 문제를 제작했는지 알 수 있는데, 이번 문제는 $0 \le S \le 100, 0 \le T \le 10000$ 조건을 가지고 있고, $S$의 최대가 $100$이므로 $a, b, c$모두를 0부터 100까지 3중 반복문으로 모든 경우의 수를 계산해도 충분히 시간제한에 걸리지 않는다.

정답 코드

#include <iostream>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int s, t; cin >> s >> t;
    int ans = 0;
    for(int i = 0; i <= 100; i++){
        for(int j = 0; j <= 100; j++){
            for(int k = 0; k <= 100; k++){
                if(i + j + k <= s && i * j * k <= t) ans++;
            }
        }
    }
    cout << ans;
    return 0;
}

C - Distribution (*319)

접기/펼치기

문제 설명
생물 $N$마리가 원을 이루며 위치해있다. 반시계방향으로 각각 $1$번, $2$번, $...$ $N$번째 생물이다.

생물 $i(1 \le i \le N)$가 시간 $t$에 보석을 받을때, $S_i$시간이 지나면 그 생물은 자신이 가지고 있는 보석을 $i + 1$번째 생물에게 $t + S_i$시간에 건네준다. 그리고 $N + 1$번째 생물은 생물 $1$이다.

추가적으로 생물 $i$는 시간 $T_i$에 보석을 따로 건네준다.

각 $i (1 \le i \le N)$에 대해서 생물 $i$가 처음으로 보석을 받게되는 시간을 구하시오. 보석을 건네는 시간은 무시한다고 가정한다.

문제 해설
구현 능력을 테스트하는 문제이다. 결국 $i$번째 생물이 보석을 받을 수 있는 경우는 총 2가지이다.

1. $T_i$에 보석을 받는다.
2. $i - 1$번째 생물에게 보석을 건네받는다.

1번 경우는 단순하다. $T_i$가 곧 보석을 받는 시간이다.
2번 경우는 조금 복잡하다. 그러면 이것부터 생각해보자. 가장 처음 보석을 받게되는 생물은 누굴까? 2번 경우는 이미 누군가가 보석을 가져야 한다는 조건이 있다. 그러면 제일 처음에 보석을 받으려면 누군가가 이 생물에게 보석을 건네주어야하고, $T_i$가 가장 작은 생물이 제일 먼저 보석을 받고 이 생물 부터 보석을 반시계방향으로 건네줄 것이다.

$T_i$가 가장 작은 생물을 $k$라고 하면 $k$가 처음 보석을 받은 시간은 $T_i$인 것은 자명하다. 그러면 $k + 1$번째 생물은? $T_k$와 $k$가 보석을 받은 시간 + $S_i$랑 작은 값이 그 답일 것이다. 이때 $k$가 보석을 받은 시간은 계속 누적하기 때문에 보석을 받은 시간을 관리하는 배열을 따로 관리하고, 그 배열값을 이용해서 최솟값을 계속 비교하며 갱신하면 답을 구할 수 있다. 이 문제의 핵심은 경우의 수 찾기라고 생각한다.

정답 코드

#include <iostream>
#include <algorithm>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int n; cin >> n;
    int s[n], t[n], ans[n];
    for(auto& x : s) cin >> x;
    for(auto& x : t) cin >> x;
    int mi = min_element(t, t + n) - t;
    ans[mi] = t[mi];
    for(int i = mi; i < mi + n; i++){
        ans[(i + 1) % n] = min(t[(i + 1) % n], ans[i % n] + s[i % n]);
    }
    for(auto x : ans) cout << x << "\n";
    return 0;
}

D - Sum of Maximum Weights (*1341)

접기/펼치기

문제 설명
$1$ 부터 $N$까지 번호가 부여되어 있는 $N$개 노드로 이루어진 트리가 있다. $i$번째 간선 $(1 \le i \le N - 1)$은 노드 $u_i$와 노드 $v_i$를 가중치 $w_i$로 연결되어 있다.

모든 다른 정점 $u, v$에 대해서 $f(u, v)$를 정점 $u$에서 $v$까지 최단 경로로 이동할 때, 지나가는 간선들 중 최대 가중치라고 정의하자.

$\sum_{i = 1}^{N - 1}{\sum_{j = i + 1}^{N}{f(i, j)}}$ 를 구하시오

문제 해설
사실 이런 최단거리의 개수를 구하는 문제에서 DSU를 사용할 줄은 꿈에도 몰랐다. 사실 아직도 어떨때 DSU를 사용하는지 감이 잡히지 않는다. 이 문제는 어떻게 풀 수 있을까?

가중치를 내림차순으로 일단 정렬을 한다. 현재 간선이 $k$라고 하면 $k$에 연결된 두 노드에 집중해보자. 내림차순으로 정렬을 했기 때문에 현재 이 간선의 가중치보다 큰 가중치는 없다. 만약 두 노드에 각각 연결된 다른 노드가 없다면 1대 1 연결이 되고, $u$에서 $v$까지 최단거리로 이동하는 $f(u, v)$ 값은 현재 가중치가 될 것이다.

만약 이 두 노드에 다른 노드가 연결되어 있다면 $u$에 연결되어 있는 노드에서 $v$에 연결되어 있는 노드로 최단거리로 이동할때 반드시 $k$를 지나야 한다. 그런데 우리의 전제 조건은 $k$보다 큰 가중치는 정렬을 통해서 배제한 상황이다. 따라서 $u \times v$개 노드 쌍만큼 $k$를 지나야 한다는 것이다. 따라서 DSU로 노드들의 집합과 개수를 관리해주고, 두 노드가 연결될 때 마다 각 노드에 있는 다른 노드의 개수를 파악해서 그쌍만큼 현 가중치를 더하는 과정을 모든 간선에 대해 반복한다면 답을 구할 수 있다.

정답 코드

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

using ll = long long;

int root[100010];
int cnt[100010];

int find(int x){
    if(x == root[x]) return x;
    return root[x] = find(root[x]);
}

void merge(int u, int v){
    u = find(u), v = find(v);
    if(u == v) return;
    root[u] = v;
    cnt[v] += cnt[u];
}


int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    vector<pair<int, pair<int, int>>> g;
    int n; cin >> n;
    for(int i = 0; i <= n; i++) cnt[i] = 1, root[i] = i;
    for(int i = 0; i < n - 1; i++){
        int u, v, w; cin >> u >> v >> w;
        g.push_back({w, {u, v}});
    }
    sort(g.begin(), g.end());
    ll ans = 0;
    for(auto x : g){
        int u = x.second.first, v = x.second.second, w = x.first;
        ans += w * 1LL * cnt[find(u)] * cnt[find(v)];
        merge(u, v);
    }
    cout << ans;
    return 0;
}