AtCoder Beginner Contest 226

https://atcoder.jp/contests/abc226/tasks

 

오랜만에 해서 그런가, 아무튼 이번 주 난이도가 꽤 쉬워보임.

 

A. Round decimals

llround(x) 함수를 쓰든

y = (int) x 를 한 다음에 x와 y+0.5와의 크기관계를 보고 올림/내림을 하면 된다.

 

B. Counting Arrays

i) set<vector<int>>를 이용하여 원소의 개수를 답으로 제출하면 됨

ii) vector<vector<int>>에 모두 넣어두고 sort한 다음에 인접한 애들끼리 비교하면 됨

 

C. Martial artist

BFS든 DFS이든 n번 기술을 배우기 전에 필요한 모든 기술을 다 체크하고, 마지막에 시간의 총합을 구하면 됨

 

D. Teleportation

어떤 움직임 (m, n)에 대하여 g = gcd(m, n)이라면 (m/g, n/g)를 배우는 것이 무조건적으로 더 이득이다.

따라서 set<pii>에 모두 넣어두고 원소의 수를 구하면 된다.

(당연히 m과 n 중에 0인 것이 있다면 gcd가 이상해지기 때문에 {0, 1}, {1, 0}, {0, 0}등으로 해야한다.)

 

E. Just one

답지의 코드가 상당히 이쁘다.

#include <bits/stdc++.h>
 
using namespace std;
 
#define N 200100
#define MOD 998244353
#define ll long long
#define rep(i, n) for(int i = 0; i < n; ++i)
#define pb push_back
 
vector<int>e[N];
bool used[N];
int x, y;
void dfs(int k) {
    used[k] = true;
    x++;
    y += e[k].size();
    rep(i, e[k].size())if (!used[e[k][i]])dfs(e[k][i]);
    return;
}
 
int main(void) {
    int n, m;
 
    ll ans = 1;
    cin >> n >> m;
    rep(i, n)used[i] = false;
    rep(i, m) {
        cin >> x >> y;
        e[x - 1].pb(y - 1);
        e[y - 1].pb(x - 1);
    }
    rep(i, n) {
        if (!used[i]) {
            x = 0;
            y = 0;
            dfs(i);
            if (y == (x * 2))ans = (ans * 2) % MOD;
            else ans = 0;
        }
    }
    cout << ans << endl;
 
    return 0;
}
 

결국 언제 ans = 0이 되느냐가 포인트이다.

어차피 하나의 cycle 비슷한 모양당 방향이 두 가지라서 가능하기만 하다면 2^(cycle 수)이기 때문이다.

답지에서 상당히 자세하게 왜 y = 2x임이 보장되어야하는지는 증명되어 있는 듯하다.

그냥 조금 더 감각적으로 접근한다면 cycle 모양이 되는 곳이 단 하나만 있어야 하기 때문에 v = e가 성립해야한다.

이때 결국 \(y = \sum{e[k].size()}\)가 간선의 수의 두 배이므로 꼭짓점의 수인 두 배와 이것이 같으면 된다.

 

조금 더 감각적이지만 복잡하게 간다면

만일 e[k].size()가 1이라면, 점 k에서 나가는 간선은 반드시 그 간선이 되어야 한다. 이후 이 간선을 없애준다.

이 과정을 반복해서 e[k].size()가 1인 점이 없도록 한다.

이후에는 모든 점들이 오직 순수한 cycle로만 남아야 하기 때문에

모두 e[k].size()가 2가 되고 BFS로 정말 cycle들이 잘 만들어졌는지 확인하며 동시에 그 개수를 세주면 된다.

signed main(void) {
    IOS;
 
    int n, m; cin >> n >> m;
    vector<multiset<int>> adj(n);
    for (int i = 0; i < m; i++) {
        int u, v; cin >> u >> v;
        u--, v--;
        adj[u].insert(v);
        adj[v].insert(u);
    }
    if (n != m) { cout << 0; return 0; }
    vi check(n);
    bool able = true;
    vi asize(n);
    queue<int> q;
    for (int i = 0; i < n; i++) {
        asize[i] = adj[i].size();
        if (asize[i] == 1) q.push(i);
        if (asize[i] == 0) able = false;
    }
    while (!q.empty()) {
        int x = q.front(); q.pop();
        if (adj[x].size() == 0) {
            able = false;
            break;
        }
        else {
            check[x] = 1;
            adj[*adj[x].begin()].erase(x);
            asize[*adj[x].begin()]--;
            if (asize[*adj[x].begin()] == 1) q.push(*adj[x].begin());
            adj[x].clear();
            asize[x]--;
        }
    }
    int g = 0;
    for (int i = 0; i < n; i++) {
        if (asize[i] != 0 && asize[i] != 2) {
            able = false;
            break;
        }
        if (check[i]) continue;
        g++;
        queue<int> q1; q1.push(i);
        while (!q1.empty()) {
            int x = q1.front(); q1.pop();
            for (auto it = adj[x].begin(); it != adj[x].end(); it = next(it)) {
                if (check[*it]) continue;
                check[*it] = 1;
                q1.push(*it);
            }
        }
    }
    if (!able) { cout << 0; return 0; }
    else cout << modpow(2, g);
}

 

F. Score of Permutations

가능한 Score의 개수가 많지 않다는 것을 깨닳으면 map으로 그냥 각 점수당 몇 개의 순열이 존재하는지 세면 된다.

우선 score이 어떻게 만들어지는지 보자. 

어떤 순열 S에 대해 (1, 2, ... n)과 S가 대응되는 함수를 생각하자.  ex) {1, 2} -> {2, 1} f(1) = 2, f(2) = 1

그러면 원소마다 어떤 cycle을 형성하게 될 것이다. Score는 결국 이 cycle들의 크기의 최소공배수이다.

합이 50 이하인 숫자들의 최소공배수가 그렇게 많이 존재하지는 않는다.

그래서 결국 n = 2부터 n = 50까지 그냥 어떤 점수를 가지는 순열의 수가 몇 개 존재하는지 모두 세면 된다.

signed main(void) {
    IOS;
    make_com();
    int n, k; cin >> n >> k;
    vector<map<int, int>> m(51);
    m[0][1] = 1;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= i; j++) {
            for (auto it = m[i - j].begin(); it != m[i - j].end(); it = next(it)) {
                int push = lcm(it->first, j);
                m[i][push] += P(i - 1, j - 1) * it->second;
                m[i][push] %= MOD;
            }
        }
    }
    int ans = 0;
    for (auto it = m[n].begin(); it != m[n].end(); it = next(it)) {
        ans += modpow(it->first, k) * it->second;
        ans %= MOD;
    }
    cout << ans;
}

m[i][j]는 길이가 i일 때 점수가 j인 순열의 수를 의미한다.

m[i]에서 m[i+1]로 갈때에는 새롭게 추가되는 원소가 길이 얼마의 cycle을 만들지 생각해서 점화식을 만들었다.

(마지막 원소가 길이 j짜리 cycle을 만든다면 이 cycle을 결정하는게 P(i-1, j-1), 점수는 lcm(기존점수, j))

 

G. The baggage

이거 그냥 솔직히 5라서 겁나 쉽게 풀었고, 머릿속으로 대충 납득도 가서 바로 답을 제출함.

자기 무게와 동일한 가방이 있다면 그것을 드는게 이득이고, 그 이후에는 최대한 제일 무거운 것을 드는게 나음.

5이하이기 때문에 놀랍게도 반례 없음

signed main(void) {
    IOS;
    int t; cin >> t;
    while (t--) {
        vi a(6), b(6);
        for (int i = 1; i <= 5; i++) cin >> a[i]; //parcel
        for (int i = 1; i <= 5; i++) cin >> b[i]; //power
        bool able = true;
        for (int i = 1; i <= 5; i++) {
            int plus = min(a[i], b[i]);
            a[i] -= plus;
            b[i] -= plus;
        }
        for (int i = 5; i > 0; i--) {
            if (b[i] < a[i]) able = false;
            for (int j = i; j > 0; j--) {
                int plus = min(b[i], a[j]);
                b[i - j] += plus;
                b[i] -= plus;
                a[j] -= plus;
            }
        }
        if (able) cout << "Yes" << endl;
        else cout << "No" << endl;
    }
 
}