Codeforces Round #635 (Div. 1, Div. 2)

A - Ichihime and Triangle

Problem - A - Codeforces

양의 정수 \(a, b, c, d\)가 주어진다.

 

1. \(a \le x \le b\)

2. \(b \le y \le c\)

3. \(c \le z \le d\)

4. 세 변의 길이가 각각 \(x, y, z\)인 삼각형이 존재한다.

 

위의 조건을 만족하는 \(x, y, z\)중 아무거나 하나 출력해야 한다.

 

\(x = b\), \(y = c\), \(z = c\)는 위의 조건을 만족한다.

 

#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; }
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    int  t; cin >> t;
    while (t--)
    {
        int a, b, c, d; cin >> a >> b >> c >> d;
        cout << b << ' ' << c << ' ' << c << '\n';
    }
}

---

B - Kana and Dragon Quest game

Problem - B - Codeforces

체력이 \(x\)인 드래곤이 있다.

 

이 드래곤에게 각각의 스킬을 사용할 수 있는데,

 

1. 현재 드래곤의 체력을 \(\lfloor \frac x2 \rfloor+ 10\)로 바꾼다.

2. 현재 드래곤의 체력을 \(x-10\)으로 바꾼다.

 

1번 스킬을 최대 \(n\)번, 2번 스킬을 최대 \(m\)번 쓸 수 있다고 할 때,

이 드래곤의 체력을 0이하로 만들 수 있는지 여부를 알아내야 한다.

 

현재 드래곤의 체력이 20이하라면, 1번 스킬을 사용하는 의미가 없음을 알 수 있다.

1번 스킬을 이용해 체력이 20이하가 될 때까지 최대한 깎은 다음,

남은 체력을 2번 스킬만으로 처리할 수 있는지 확인하면 된다.

 

#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; }
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    int t; cin >> t;
    while (t--)
    {
        int x, n, m; cin >> x >> n >> m;
        for (int i = 0; i < n; i++)
        {
            int y = x / 2 + 10;
            if (x > y) x = y;
        }
 
        if (x <= 10 * m) cout << "YES\n";
        else cout << "NO\n";
    }
}

---

A - Linova and Kingdom

Problem - A - Codeforces

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

이 정점들 중 정확히 \(k\)개를 골라 색칠하려고 한다.

 

모든 색칠한 정점에서 루트까지 가는 경로 중에서, 색칠되지 않은 정점의 개수 합을 이 트리의 점수라고 하자.

트리를 적절히 색칠 했을 때 얻을 수 있는 트리의 점수의 최대값을 구해야 한다.

 

먼저 당연히 (루트가 아닌) 리프 노드를 먼저 칠하는게 가장 이득임을 알 수 있다.

더 일반적으로, 어떤 정점을 칠하고 싶다면 그 자식들이 이미 칠해진 후에 칠하는 것이 이득임을 알 수 있다.

그렇다면 어떤 정점 \(v\)를 칠했을 때, 더해지는 점수는 다음과 같다.

\(len_v - child_v\) (\(len_v : \) 루트에서 \(v\)까지의 거리, \(child_v : \) \(v\)의 모든 자식의 수)

 

이 값들을 우선순위 큐 등으로 관리해서, 현재 상황에서 더해지는 점수가 가장 큰 정점을 칠하는 것을 반복하면 된다.

 

#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, k;
vector <int> graph[200001];
 
int par[200001];
ll len[200001];
ll child[200001];
ll oq[200001];
 
priority_queue <pii> pq;
 
int DFS(int v, int p, ll l)
{
    len[v] = l;
    par[v] = p;
    child[v] = 0;
 
    oq[v] = graph[v].size();
    if (v != 1) oq[v]--;
 
    for (auto nv : graph[v])
    {
        if (nv == p) continue;
        child[v] += DFS(nv, v, l + 1);
    }
 
    if (v != 1 && graph[v].size() == 1) pq.push({ len[v], v });
 
    return child[v] + 1;
}
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    cin >> n >> k;
    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, 0);
    ll ans = 0;
 
    for (int i = 0; i < k; i++)
    {
        pll tmp = pq.top(); pq.pop();
        ans += tmp.first;
 
        int v = tmp.second;
        int p = par[v];
 
        if (--oq[p] == 0)
        {
            pq.push({ len[p] - child[p] ,p });
        }
    }
 
    cout << ans;
}

---

B - Xenia and Colorful Gems

Problem - B - Codeforces

\(n_r\)개의 수로 이루어진 수열 \(r\),

\(n_g\)개의 수로 이루어진 수열 \(g\),

\(n_b\)개의 수로 이루어진 수열 \(b\)이 주어진다.

 

3개의 수열에서 한 개씩의 수를 골라 각각 \(x, y, z\)라고 할 때,

\((x-y)^2+(y-z)^2+(z-x)^2\)의 최소값을 알아내야 한다.

 

\(r\)에서 수 하나를 고르고 이것을 \(r_i\)라고 하자.

\(g\)와 \(b\)각각에서 \(r_i\)와의 차가 가장 적은 원소들을 이분탐색으로 찾을 수 있다.

 

이 원소들을 이용해 위의 식을 계산하고, 이를 수열 \(g\)와 \(b\)에 대해서도 반복하면 이 중 적어도 하나는 답이 됨을 관찰로써 알 수 있다.

 

#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; }
 
const ll INF = 2e9;
 
int n[3];
vector <ll> w[3];
 
ll calc(ll r, ll g, ll b)
{
    return (r - g) * (r - g) + (g - b) * (g - b) + (b - r) * (b - r);
}
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    int t; cin >> t;
    while (t--)
    {
        for (int k = 0; k < 3; k++) w[k].clear();
        for (int k = 0; k < 3; k++) cin >> n[k];
        for (int k = 0; k < 3; k++)
        {
            for (int i = 0; i < n[k]; i++)
            {
                ll x; cin >> x;
                w[k].push_back(x);
            }
 
            sort(w[k].begin(), w[k].end());
        }
 
        ll ans = numeric_limits<ll>::max();
        for (int k = 0; k < 3; k++)
        {
            vector <ll>& r = w[k];
            vector <ll>& g = w[(k + 1) % 3];
            vector <ll>& b = w[(k + 2) % 3];
 
            for (int i = 0; i < n[k]; i++)
            {
                ll cr = r[i];
                
                ll cg[2] = { INF, INF };
                auto it = lower_bound(g.begin(), g.end(), cr);
                if (it == g.end())
                    cg[0] = g.back();
                else
                {
                    cg[0] = *it;
                    if (it != g.begin()) cg[1] = *prev(it);
                }
 
                ll cb[2] = { INF, INF };
                it = lower_bound(b.begin(), b.end(), cr);
                if (it == b.end())
                    cb[0] = b.back();
                else
                {
                    cb[0] = *it;
                    if (it != b.begin()) cb[1] = *prev(it);
                }
 
                for (int u = 0; u < 2; u++) for (int v = 0; v < 2; v++)
                {
                    ll res = calc(cr, cg[u], cb[v]);
                    ans = min(ans, res);
                }
            }
        }
 
        cout << ans << '\n';
    }
}

---

C - Kaavi and Magic Spell

Problem - C - Codeforces

길이 \(n\)의 문자열 \(S\)와 길이 \(m\)의 문자열 \(T\)가 주어진다.

 

\(S\)와 빈 문자열 \(A\)에 대해, 다음과 같은 연산을 하려고 한다.

1. \(S\)의 맨 앞 문자를 삭제하고, \(A\)의 맨 앞에 붙인다.

2. \(S\)의 맨 앞 문자를 삭제하고, \(A\)의 맨 뒤에 붙인다.

 

이 연산을 최대 \(n\)번 했을 때, \(A\)의 접두사가 \(T\)가 되도록 하는 서로 다른 연산 방법의 수를 알아내야 한다.

 

\(DP(i, j)\)를 다음과 같이 정의하자.

\(DP(i, j) : \) S의 첫 \(j-i+1\)개의 문자를 이용해 \(T\)의 부분 문자열 \(T[i, j]\)를 만드는 경우의 수

이 때 이 부분 문자열은 문자 \(S_{j-i}\)를 맨 앞이나 맨 뒤에 붙인 결과물임을 알 수 있다.

 

따라서 다음과 같은 점화식을 얻을 수 있다.

$$DP(i, j) = DP(i+1, j) _{\text{if }S_{j-i} = T_i} + DP(i, j-1) _{\text{if }S_{j-i} = T_j}$$

 

\(A\)의 길이는 최소 \(m\), 최대 \(n\)이므로, 각각에 대해 \(DP(0, |A|-1)\)을 구하면 된다.

이 경우 만약 \(i\)나 \(j\)가 \(m\)보다 크거나 같다면, 어떤 문자에도 대응되도록 하면 된다.

 

총 시간복잡도 \(O(n^2)\)로 답을 구할 수 있다.

 

#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; }
 
const ll MOD = 998244353;
 
string s, t;
ll dp[3001][3001];
 
ll solve(int i, int j)
{
    if (i > j) return 1;
    ll& ret = dp[i][j];
    if (ret != -1) return ret;
 
    int idx = j - i;
 
    ret = 0;
    if (i >= t.size() || t[i] == s[idx])
    {
        ret += solve(i + 1, j);
        ret %= MOD;
    }
 
    if (j >= t.size() || t[j] == s[idx])
    {
        ret += solve(i, j - 1);
        ret %= MOD;
    }
 
    return ret;
}
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    cin >> s >> t;
 
    memset(dp, -1, sizeof dp);
 
    ll ans = 0;
    for (int i = t.size() - 1; i < s.size(); i++)
    {
        ans += solve(0, i);
        ans %= MOD;
    }
 
    cout << ans;
}

---

D - Yui and Mahjong Set

Problem - D - Codeforces

추가 예정

---

E - Chiori and Doll Picking (hard version)

Problem - E2 - Codeforces

추가 예정

---

F - Journey

Problem - F - Codeforces

추가 예정