Codeforces Round #660 (Div. 2)

A - Captain Flint and Crew Recruitment

Problem - A - Codeforces

정수 \(n\)이 주어진다.

nearly prime은 서로 다른 두 소수의 곱으로 나타낼 수 있는 정수를 말한다.

\(n\)을 서로 다른 4개의 양의 정수의 합으로 나타내야 하는데, 그 중 적어도 3개가 nearly prime일 수 있는지 여부를 알아내고,

가능하다면 실해를 출력해야 한다.

 

가장 작은 3개의 nearly prime인 6, 10, 14와 \(n-30\)을 하면 일반적으로 답이다.

\(n-30\)이 6, 10, 또는 14와 같거나 양의 정수가 아닐 경우 각각 예외처리를 해주면 된다.

 

#include <bits/stdc++.h>
using namespace std;
 
typedef unsigned long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
 
ll gcd(ll a, ll b) { for (; b; a %= b, swap(a, b)); return a; }
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    int t; cin >> t;
    while (t--)
    {
        int n; cin >> n;
        if (n < 31) cout << "NO\n";
        else
        {
            cout << "YES\n";
 
            if (n - 30 == 6)
            {
                cout << "5 6 10 15\n";
            }
            else if (n - 30 == 10)
            {
                cout << "6 9 10 15\n";
            }
            else if (n - 30 == 14)
            {
                cout << "6 7 10 21\n";
            }
            else
            {
                cout << "6 10 14 " << n - 30 << '\n';
            }
        }
    }
}

---

B - Captain Flint and a Long Voyage

Problem - B - Codeforces

\(n\)자리로 이루어진 양의 정수 \(x\)가 주어진다.

이 정수의 각각의 자리를 이진수로 바꾸고, 이를 \(k\)라고 하자.

마지막으로 \(k\)의 마지막 \(n\)자리를 삭제했을 때, 이 값이 최대가 되는 \(n\)중 최소값을 알아내야 한다.

 

우선 각 자리수를 이진수로 바꿨을 때 길이가 길수록 이득임을 알 수 있다. 따라서 각 자리는 8또는 9여야 한다.

\(k\) 마지막 \(n\)자리를 삭제할 때 영향을 받는 자리수는 8, 그렇지 않는 자리수는 9로 하면 답이다.

 

#include <bits/stdc++.h>
using namespace std;
 
typedef unsigned long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
 
ll gcd(ll a, ll b) { for (; b; a %= b, swap(a, b)); return a; }
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    int t; cin >> t;
    while (t--)
    {
        int n; cin >> n;
        int er = (n - 1) / 4 + 1;
        for (int i = 0; i < n; i++)
        {
            if (i + er < n) cout << 9;
            else cout << 8;
        }
        cout << '\n';
    }
}

---

C - Uncle Bogdan and Country Happiness

Problem - C - Codeforces

\(n\)개의 정점으로 이루어진 트리가 있다. 1번 정점이 루트이다.

\(m\)명의 사람들이 있고, 사람들은 1번 정점에서 일을 한 다음 본인의 집이 있는 정점으로 이동한다.

각각의 사람들은 퇴근할 때 기분이 좋을 수도 있고, 나쁠 수도 있다.

또 퇴근길에 정점 사이를 이동하면서, 기분이 좋았던 사람이 기분이 나빠질 수도 있다.

한 번 기분이 나빠진 다음에는 다시 기분이 좋아지지 않는다.

 

각 정점에 대해 행복도 \(h_i\)가 주어진다.

이 값은 퇴근길에 \(i\)번 정점을 들른 모든 사람에 대해, 이 정점에 있을 때 기분이 좋았던 사람의 수에서 기분이 나빴던 사람의 수를 뺀값이다.

 

각 정점이 집인 사람의 수들이 주어졌을 때, 모든 정점 \(i\)에 대하여 행복도 \(h_i\)가 되도록 하는것이 가능한지 알아내야 한다.

 

반대로, 리프에서부터 루트까지 올라가면서 문제를 해결해 보자.

초기에 사람들은 모두 기분이 좋지 않고, 중간에 올라가면서 기분이 좋아질 수 있다.

 

현재 어떤 리프노드에 대해, 사람 수가 부족하거나 이미 행복한 사람들이 있는 등 현재 사람들로 각 정점의 행복도를 만들 수 없다면 불가능하다.

각 리프 노드를 처리했으면 이 노드를 삭제하고, 다른 리프노드를 골라서 루트 노드를 처리할 때까지 반복하면 된다.

 

#include <bits/stdc++.h>
using namespace std;
 
typedef unsigned long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
 
ll gcd(ll a, ll b) { for (; b; a %= b, swap(a, b)); return a; }
 
int n, m;
int p[100001];
int h[100001];
 
vector <int> graph[100001];
int par[100001];
int child[100001];
int cgood[100001], cbad[100001];
 
void DFS(int v, int pr)
{
    par[v] = pr;
    child[v] = 0;
    cgood[v] = 0, cbad[v] = p[v];
 
    for (int nv : graph[v])
    {
        if (nv == pr) continue;
        child[v]++;
        DFS(nv, v);
    }
}
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    int t; cin >> t;
    while (t--)
    {
        cin >> n >> m;
        for (int i = 1; i <= n; i++) cin >> p[i];
        for (int i = 1; i <= n; i++) cin >> h[i];
 
        for (int i = 1; i <= n; i++) graph[i].clear();
        for (int i = 0; i < n - 1; i++)
        {
            int u, v; cin >> u >> v;
            graph[u].push_back(v);
            graph[v].push_back(u);
        }
 
        DFS(1, 0);
 
        bool ans = true;
        queue <int> q;
        for (int i = 1; i <= n; i++) if (child[i] == 0) q.push(i);
 
        while (!q.empty())
        {
            int v = q.front(); q.pop();
            int ch = cgood[v] - cbad[v];
            int mx = cgood[v] + cbad[v];
            if (h[v] < ch || h[v] > mx || (h[v] - ch) % 2 == 1)
            {
                ans = false;
                break;
            }
 
            int inv = (h[v] - ch) / 2;
            cgood[v] += inv;
            cbad[v] -= inv;
 
            if (par[v] && --child[par[v]] == 0) q.push(par[v]);
            cgood[par[v]] += cgood[v];
            cbad[par[v]] += cbad[v];
        }
 
        if (ans) cout << "YES\n";
        else cout << "NO\n";
    }
}

---

D - Captain Flint and Treasure

Problem - D - Codeforces

\(n\)의 길이를 가지는 배열 \(a,b\)가 있다.

초기에 \(ans\)변수에 0이 할당되어있고, 다음의 연산을 할 수 있다.]

 

1. 인덱스 \(i\)를 고른다.

2. \(a_i\)를 \(ans\)에 더한다.

3. \(b_i\)가 -1이 아니라면 \(a_i\)를 \(a_{b_i}\)에 더한다.

 

각각의 인덱스 \(i\)를 한 번씩 고를 수 있을 때, 얻을 수 있는 \(ans\)값의 최대값을 알아내야 한다.

 

문제를 \(i\)의 부모가 \(b_i\)인 포레스트로 생각해보자.

만약 \(a_i\)가 전부 양수라면, 리프노드 부터 시작해서 최대한 같은 수를 여러번 더하는 것이 이득임을 알 수 있다.

 

C번과 같이 리프노드부터 시작해 문제를 해결하자.

현재 \(a_i\)에 저장된 값이 음수가 아니라면, 바로 \(ans\)에 \(a_i\)를 더한다. \(a_{b_i}\)에 \(a_i\)를 더한다.

하지만 음수라면, 이 수를 여러번 더하는 것은 이득이 될 수 없기때문에, 지금 계산하는 것은 무조건 손해이다.

따라서 \(a_i\)가 음수인 모든 점은 음수가 아닌 점이 모두 계산된 후에, 만난 순서의 역순으로 처리하면 무조건 한 번씩만 계산되도록 할 수 있고, 이 방법이 최선임을 알 수 있다.

 

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
 
ll gcd(ll a, ll b) { for (; b; a %= b, swap(a, b)); return a; }
 
ll n;
ll a[200001];
ll b[200001];
 
int par[200001];
int child[200001];
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= n; i++)
    {
        int b; cin >> b;
        par[i] = b;
        child[b]++;
    }
 
    queue <int> q;
    for (int i = 1; i <= n; i++) if (child[i] == 0) q.push(i);
 
    ll ans = 0;
    vector <int> p;
    vector <int> inv;
 
    while (!q.empty())
    {
        int v = q.front(); q.pop();
        ans += a[v];
 
        if (a[v] >= 0)
        {
            p.push_back(v);
            if (par[v] != -1) a[par[v]] += a[v];
        }
        else
        {
            inv.push_back(v);
        }
 
        if (par[v] != -1 && --child[par[v]] == 0) q.push(par[v]);
    }
 
    reverse(inv.begin(), inv.end());
 
    cout << ans << '\n';
    for (int v : p) cout << v << ' ';
    for (int v : inv) cout << v << ' ';
}

---

E - Uncle Bogdan and Projections

Problem - E - Codeforces

추가 예정