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

https://codeforces.com/contest/1646

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

 

 

A. Square Counting

풀이

• n + 1 개 중 $a[i] = n^2 $인 원소의 개수를 x 라 하면
• $s = x * n^2 + R$ 이고 $R = (n + 1 - x) * (0...n - 1)$ 이다
• R 의 최대가 $n^2 - 1$ 이므로 
• 구하는 답은 $ S / N^2 $ 이다

코드

#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--) {
        long long N, S;
        cin >> N >> S;

        cout << S / (N * N) << '\n';
    }
}

 

B. Quality vs Quantity

풀이

• 빨간색 개수보다 파란색 개수가 한개 더 많은 것이 개수 조건을 만족하면서, 합조건을 만족하기에 최선이다.
• 파란색 집합에는 작은것, 빨간색 집합에는 큰것이 들어가는 것이 합조건을 만족하기에 최선이다.
• 배열 오름차순 정렬후 파란색을 앞에서부터, 빨간색을 뒤에서부터 개수 증가시켜가면서 조건 만족하는 것 있는지 찾기

코드

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

#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> a(N), pa(N, 0);
        for (int i = 0; i < N; ++i) {
            cin >> a[i];
        }
        sort(all(a));
        for (int i = 0; i < N; ++i) {
            pa[i] = a[i];
            if (i) pa[i] += pa[i - 1];
        }
        

        bool yes = false;
        for (int i = 2; i < N; ++i) {
            if (i + i - 1 > N) break;
            if (pa[i - 1] < pa[N - 1] - pa[N - i]) {
                yes = true;
                break;
            }
        }

        if (yes) {
            cout << "YES\n";
        } else {
            cout << "NO\n";
        }
    }
}

 

C. Factorials and Powers of Two

풀이

• powerful number 는 겹치지 않는 두 집합으로 나눌 수 있다.
  • $2^d$ : $1, 2, 4, 8, ... $
  • $3!, 4!, 5!, ...$
• $10^{12}$ 를 넘지 않는 팩토리얼은 $14!$ 이므로 모든 조합의 수는 $2^{12} - 1$ 이다.
• N 넘지 않는 모든 팩토리얼 합에 대해서 개수를 구해주고 최소를 구하면 된다.

코드

• 시간복잡도: $O(2^{12})$

#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);

    vector<long long> fac(15, 1);
    for (int i = 1; i < 15; ++i) {
        fac[i] = fac[i - 1] * i;
    }
    
    int TC; cin >> TC;
    while (TC--) {
        long long N;
        cin >> N;
        long long ans = 1e9;
        for (long long i = 0; i < (1 << 12); ++i) {
            long long cnt1 = 0, cnt2 = 0;
            long long factSum = 0;

            for (long long j = 0; j < 12; ++j) {
                if (i & (1LL << j)) {
                    factSum += fac[j + 3];
                    ++cnt1;
                }
            }

            long long tmp = N - factSum;
            if (tmp < 0) break;
            while (tmp) {
                if (tmp & 1) ++cnt2;
                tmp >>= 1;
            }

            ans = min(ans, cnt1 + cnt2);
        }
        cout << ans << '\n';
    }
}

 

D. Weight the Tree

풀이

• N = 2 인 경우를 제외하고, 한 간선의 양 끝 정점이 모두 good 일 수 없다.
• not good 일 때는 value 가 1 일 때 최소 합을 가진다.
• $dp[i][g]: $ i 정점이 good: g 이고 i 루트로 가지는 서브트리의 {최대 good 개수, 최소 합} 으로 정의
• $dp[i][g]$ 를 구할 때 g 가 true 이면( good 이면) 그 아래 정점들은 무조건 not good 이지만, g 가 false 면 그 아래 정점들이 good, not good 두가지 모두 따져야 원하는 dp 값을 구할 수 있다.

코드

• 시간복잡도:$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 N;
    cin >> N;

    if (N == 2) {
        cout << "2 2\n";
        cout << "1 1\n";
        return 0;
    }
    vector<vector<int> > adj(N + 1);

    for (int i = 0; i < N - 1; ++i) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    vector<vector<pair<int, int> > > dp(N + 1, vector<pair<int, int> > (2, {-1, -1}));
    function<pair<int, int>(int, int, int)> f = [&](int cur, int g, int p) {
        auto& ret = dp[cur][g];

        if (ret.first != -1) {
            return ret;
        }

        if (g) {
            ret = {g, -adj[cur].size()};
            for (auto e: adj[cur]) {
                if (e == p) continue;
                ret.first += f(e, !g, cur).first;
                ret.second += f(e, !g, cur).second;
            }
        } else {
            // not good
            ret = {g, -1};
            for (auto e: adj[cur]) {
                if (e == p) continue;
                if (f(e, g, cur) > f(e, !g, cur)) {
                    ret.first += f(e, g, cur).first;
                    ret.second += f(e, g, cur).second;
                } else {
                    ret.first += f(e, !g, cur).first;
                    ret.second += f(e, !g, cur).second;
                }
            }
        }

        return ret;
    };

    auto ans = max(f(1, 1, -1), f(1, 0, -1));

    cout << ans.first << ' ' << -ans.second << '\n';
    
    vector<int> w(N + 1, 0);
    function<void(int, int, pair<int, int>)> f2 = [&](int cur, int p, pair<int, int> val) {
        if (val == f(cur, 0, p)) {
            w[cur] = 1;
            for (auto e: adj[cur]) {
                if (e == p) continue;
                f2(e, cur, max(f(e, 0, cur), f(e, 1, cur)));
            }
        } else {
            w[cur] = adj[cur].size();
            for (auto e: adj[cur]) {
                if (e == p) continue;
                f2(e, cur, f(e, 0, cur));
            }
        }

    };
    f2(1, -1, ans);
    for (int i = 1; i <= N; ++i) {
        cout << w[i] << ' ';
    }
    cout << '\n';
}

 

E. Power Board

풀이

• $x, x^2, ... , x^k$ 행들에서만 중복이 나올 수 있다. k 는 최대 $log_2 N$
• 각 행의 지수들은
  • $1 * 1, 1 * 2, ..., 1 * M$
  • $2 * 1, 2 * 2, ..., 2 * M$
  • $k * 1, k * 2, ..., k * M$
• k 에 따라 이 set 들에서의 distinct 한 개수가 정해진다.

코드

• 시간복잡도: $O(MlogN + 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 N, M;
    cin >> N >> M;

    vector<long long> cnt(log2(N) + 1, 0);
    vector<long long> checked((long long)(cnt.size()) * M, false);
    long long ccnt = 0;
    for (long long i = 1; i < cnt.size(); ++i) {
        for (long long j = 1; j <= M; ++j) {
            if (checked[i * j]) continue;
            checked[i * j] = true;
            ++ccnt;
        }
        cnt[i] = ccnt;
    }

    long long ans = 1;
    vector<int> counted(N + 1, false);
    for (long long i = 2; i <= N; ++i) {
        if (counted[i]) continue;

        long long tmp = i;
        long long k = 0;
        while (tmp <= N) {
            ++k;
            counted[tmp] = true;
            tmp *= i;
        }

        ans += cnt[k];
        counted[i] = true;
    }
    cout << ans << '\n';
}