Codeforces Round #711 (Div. 2)

A - GCD Sum

Problem - A - Codeforces

어떤 수 \(x\)의 gcdSum을 \(x\)와, \(x\)의 모든 자릿수의 합의 최대공약수로 정의하자.

\(n\)이 주어지면, \(n\)보다 크거나 같으면서 gcdSum이 1보다 큰 가장 작은 수를 구해야 한다.

 

어떤 수 \(x\)가 3으로 나눠 떨어진다면, gcdSum도 3의 배수이다.

따라서 \(n, n+1, 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; }
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    int t; cin >> t;
    while (t--)
    {
        ll n; cin >> n;
        while (true)
        {
            ll tn = n;
            ll sum = 0;
            while (tn)
            {
                sum += tn % 10;
                tn /= 10;
            }
 
            if (gcd(n, sum) > 1)
            {
                cout << n << '\n';
                break;
            }
 
            n++;
        }
    }
}
 

---

B - Box Fitting

Problem - B - Codeforces

높이가 1인 \(n\)개의 직사각형이 주어진다. 각 직사각형의 너비는 \(2^k\)꼴이다.

너비가 \(W\)인 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; }
 
ll n, w;
ll a[100001];
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    int t; cin >> t;
    while (t--)
    {
        cin >> n >> w;
        for (int i = 0; i < n; i++) cin >> a[i];
        sort(a, a + n);
        reverse(a, a + n);
 
        multiset <ll> st;
        st.insert(w);
 
        for (int i = 0; i < n; i++)
        {
            auto it = st.lower_bound(a[i]);
            if (it == st.end())
            {
                st.insert(w);
                it = st.lower_bound(a[i]);
            }
 
            ll x = *it;
            st.erase(it);
            st.insert(x - a[i]);
        }
 
        cout << st.size() << '\n';
    }
}
 

---

C - Planar Reflections

Problem - C - Codeforces

\(n\)개의 판이 일렬로 늘어서 있다.

판에 세기가 \(k\)의 빛을 쏘면, 세기가 \(k\)의 빛은 그대로 판을 통과하고 추가로 세기가 \(k-1\)이고 반대방향을 진행하는 빛이 생기게 된다.

세기가 1인 빛은 더 이상 반대방향으로 진행하는 빛을 생성하지 않는다.

 

맨 앞에 있는 판에 세기 \(k\)의 빛을 쐈을 때, 마지막에 빛이 총 몇개 존재하는지 알아내야 한다.

 

다음과 같은 DP를 정의해 풀 수 있다.

\(DP_{i,j} :\) 앞에 \(i\)개의 판이 있을 때, 세기가 \(j\)인 빛이 닿았을 때 생기는 총 빛의 수

 

#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 = 1e9 + 7;
 
ll n, k;
ll dp[2][1001][1001];
ll solve(int d, ll cn, ll k)
{
    if (k < 1) return 0;
    if (cn < 1 || cn > n) return 1;
    ll& ret = dp[d][cn][k];
    if (ret != -1) return ret;
 
    ret = 0;
    if (d == 0)
    {
        ll r1 = solve(0, cn + 1, k);
        ll r2 = solve(1, cn - 1, k - 1);
        ret += (r1 + r2) % MOD;
        ret %= MOD;
    }
    else
    {
        ll r1 = solve(1, cn - 1, k);
        ll r2 = solve(0, cn + 1, k - 1);
        ret += (r1 + r2) % MOD;
        ret %= MOD;
    }
 
    return ret;
}
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    int t; cin >> t;
    while (t--)
    {    
        cin >> n >> k;
 
        for (int i = 0; i <= n; i++) for (int j = 0; j <= k; j++)
        {
            dp[0][i][j] = dp[1][i][j] = -1;
        }
 
        ll ans = solve(0, 1, k);
        cout << ans << '\n';
    }
}
 

---

D - Bananas in a Microwave

Problem - D - Codeforces

오작동하는 전자레인지가 있다. 이 전자레인지에 현재 0개의 바나나가 있다.

전자레인지가 오작동하면서, 각 단계마다 바나나의 개수가 바뀌게 된다.

 

현재 전자레인지에 있는 바나나의 수를 \(k\)라고 했을 때, 각 단계에 바나나가 바뀌는 방법이 다음과 같이 주어진다.

1. \((t_i = 1, x_i, y_i)\)

0이상 \(y_i\)이하의 정수 \(a_i\)를 하나 고른다.

다음과 같은 연산을 \(a_i\)번 실행한다. \(k := \lceil k+x_i \rceil\)

 

2. \((t_i = 2, x_i, y_i)\)

0이상 \(y_i\)이하의 정수 \(a_i\)를 하나 고른다.

다음과 같은 연산을 \(a_i\)번 실행한다. \(k := \lceil k \times x_i \rceil\)

 

\([1, m]\)에 포함되는 각 \(j\)에 대하여, 정확히 \(j\)개의 바나나를 얻기 위해서는 최소 몇 단계가 필요한지 알아내야 한다.

 

다음과 같은 DP를 정의하자.

\(DP_{i,j} :\) \(i\)번째 단계에 \(j\)개의 바나나를 얻을 수 있는지 여부 (bool)

 

이를 단순하게 계산하면 \(O(nm^2)\)라서 너무 느리다.

테이블을 바텀업으로 채워나가자. \(DP_{i, j}\)가 true라면, \(DP_{i+1, ?}\)를 채울 수 있다.

\(DP_{i, j}\)가 true인지 확인할 때 \(j\)가 큰 순서대로 확인하자.

만약 \(DP_{i+1, ?}\)가 이미 true라면, 더 탐색할 필요가 없음을 알 수 있다.

 

따라서 각 단계에서 총 \(O(m)\)의 시간복잡도로 테이블을 채울 수 있다.

 

#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, m;
int ans[100001];
int cur[100001];
int nxt[100001];
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    memset(ans, -1, sizeof ans);
 
    cin >> n >> m;
    cur[0] = 1;
 
    for (int k = 1; k <= n; k++)
    {
        ll t, x, y; cin >> t >> x >> y;
 
        memset(nxt, 0, sizeof nxt);
        for (int i = m; i >= 0; i--)
        {
            if (!cur[i]) continue;
 
            if (t == 1)
            {
                ll c = i;
                for (int j = 0; j <= y && c <= m && !nxt[c]; j++)
                {
                    nxt[c] = 1;
                    c = (c * 100000 + x - 1 + 100000) / 100000;
                }
            }
            else
            {
                ll c = i;
                for (int j = 0; j <= y && c <= m && !nxt[c]; j++)
                {
                    nxt[c] = 1;
                    c = (c * x - 1 + 100000) / 100000;
                }
            }
        }
 
        memcpy(cur, nxt, sizeof cur);
        for (int i = 1; i <= m; i++)
        {
            if (!cur[i] || ans[i] != -1) continue;
            ans[i] = k;
        }
    }
 
    for (int i = 1; i <= m; i++) cout << ans[i] << ' ';
}
 

---

E - Two Houses

Problem - E - Codeforces

\(n\)개의 정점으로 이루어진 그래프가 있다.

이 그래프의 모든 서로 다른 정점 사이에는 단 1개의 방향 간선이 존재한다.

각 정점의 indegree가 주어진다. 이를 \(k_i\)라고 하자.

 

어떤 두 정점 \(u, v\)에 대해, \(u\)에서 \(v\)로 이동할 수 있고, \(v\)에서 \(u\)로 이동할 수 있으면

이 두 정점을 bi-reachable이라고 한다.

 

bi-reachable한 두 정점을 알아내야 한다.

그런 정점이 많으면 \(|k_u - k_v|\)가 가장 큰 두 정점을 출력한다.

 

이를 알아내기 위해, 두 정점 \(u, v\)를 입력으로 주면 \(u\)에서 \(v\)로 이동할 수 있는지 여부를 알려주는 쿼리를 사용할 수 있다.

단, 한번 "Yes"라는 답을 받았다면, 더는 쿼리를 사용할 수 없다.

 

 

그래프가 특수하기 때문에, 만약 \(k_u > k_v\)인 정점 \(u, v\)에 대해서 \(u\)에서 \(v\)로 가는 경로가 존재한다면 \(v\)에서 \(u\)로 가는 경로 또한 존재함을 알 수 있다.

 

따라서 \(|k_u - k_v|\)가 큰 순으로 정렬한 다음, 쿼리를 날려서 "Yes"라는 답을 받은 순간 그 두 정점을 출력하면 된다.

 

#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 n;
int k[501];
 
bool query(int a, int b)
{
    cout << "? " << a << ' ' << b << endl;
    string res; cin >> res;
    return res == "Yes";
}
 
int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> k[i];
 
    vector <pair<int, pii> > v;
    for (int i = 1; i <= n; i++) for (int j = i + 1; j <= n; j++)
    {
        int a = i, b = j;
        if (k[a] < k[b]) swap(a, b);
 
        v.push_back({ k[a] - k[b],{a,b} });
    }
 
    sort(v.rbegin(), v.rend());
    
    for (auto it : v)
    {
        int a = it.second.first, b = it.second.second;
        if (query(a, b))
        {
            cout << "! " << a << ' ' << b << endl;
            return 0;
        }
    }
 
    cout << "! 0 0" << endl;
}
 

---

F - Christmas Game

Problem - F - Codeforces

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

각 정점에는 \(a_i\)개의 선물이 있고, 이 선물을 이용해 두 사람이 게임을 하려고 한다.

 

게임 시작 전 정수 \(k\)가 주어진다.

각 차례에 플레이어는 깊이가 최소 \(k\)인 정점을 하나 고른 다음, 원하는 양의 선물을 골라 \(k\)번째 조상 노드로 옮긴다.

더 이상 진행할 수 없는 플레이어가 패배한다.

 

트리의 모든 노드에 대해, 각 노드가 트리의 루트일 때 두 플레이어가 이상적으로 플레이한다면 누가 이기는지 알아내야 한다.

 

먼저, 1번 노드가 루트일 때 문제를 해결해 보자.

우선 깊이가 \(k\)이상 \(2k\)미만인 각 정점에 대해서는, 각각 \(a_i\)개의 선물이 있는 님 게임을 진행하는 것이라고 생각할 수 있다.

 

이를 조금 더 일반적으로 생각해보자. \(\lfloor \frac{depth_i}{k} \rfloor\)가 짝수일 때만 존재한다고 생각해보면, 모든 선물을 짝수번 이동시켜줘야 한다.

선공이 어떻게 하든 패배할 수 밖에 없으므로, 이 정점들의 그런디 수는 0이라고 생각할 수 있다.

따라서 1번 노드에서, \(\lfloor \frac{depth_i}{k} \rfloor\)가 홀수인 모든 노드들에 대해, bitwise xor을 계산함으로써 누가 이길지 알 수 있다.

 

1번 노드가 루트인 트리에서, 각 노드를 루트로 하는 서브트리에 대해

깊이를 \(2k\)로 나누었을 때 나머지가 같은 모든 노드들의 bitwise xor을 계산해 놓자.

 

이 상태에서 DFS로 트리를 탐색하면서 루트를 바꿔나가보자.

현재 정점 \(v\)이 루트이고, 이 정점과 이어진 \(nv\)를 새로운 루트로 하고자 한다면,

이 두 정점에 대해서만 아까 계산한 xor값들을 갱신 시켜주면 바로 \(nv\)가 루트일 때의 값을 알 수 있음을 알 수 있다.

 

따라서 총 시간복잡도 \(O(kn)\)으로 문제를 해결할 수 있다.

 

#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 n, k;
vector <int> graph[100001];
ll a[100001];
 
ll x[41][100001];
void DFS(int v, int p)
{
    x[0][v] = a[v];
    for (int nv : graph[v])
    {
        if (nv == p) continue;
        DFS(nv, v);
 
        for (int i = 0; i < 2 * k; i++)
        {
            x[(i + 1) % (2 * k)][v] ^= x[i][nv];
        }
    }
}
 
ll ans[100001];
void DFS2(int v, int p)
{
    for (int i = k; i < k * 2; i++) ans[v] ^= x[i][v];
 
    for (int nv : graph[v])
    {
        if (nv == p) continue;
 
        for (int i = 0; i < 2 * k; i++)
        {
            x[(i + 1) % (2 * k)][v] ^= x[i][nv];
        }
 
        for (int i = 0; i < 2 * k; i++)
        {
            x[(i + 1) % (2 * k)][nv] ^= x[i][v];
        }
 
        DFS2(nv, v);
 
        for (int i = 0; i < 2 * k; i++)
        {
            x[(i + 1) % (2 * k)][nv] ^= x[i][v];
        }
 
        for (int i = 0; i < 2 * k; i++)
        {
            x[(i + 1) % (2 * k)][v] ^= x[i][nv];
        }
    }
}
 
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);
    }
 
    for (int i = 1; i <= n; i++) cin >> a[i];
 
    DFS(1, 0);
    DFS2(1, 0);
 
    for (int i = 1; i <= n; i++)
        cout << (ans[i] ? 1 : 0) << ' ';
}