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

A - Filling Diamonds

Problem - A - Codeforces

\(4n-2\)개의 삼각형으로 이루어진 도형이 있다.

이 도형을 2개의 삼각형이 이어진 다이아몬드 모양으로 덮는 방법의 수를 구해야 한다.

 

위아래로 붙은 다이아몬드 모양을 한 군데에 놓게 되면, 나머지 구간은 덮는 방법이 1가지로 고정된다.

이 다이아몬드를 놓을 수 있는 공간의 수가 \(n\)이므로, 답은 \(n\)이다.

 

#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 n; cin >> n;
        cout << n << '\n';
    }
}

---

B - Sorted Adjacent Differences

Problem - B - Codeforces

\(n\)개의 수로 이루어진 수열 \(a\)가 주어진다.

이 수열의 수들을 재배치 해서

\(|a_i - a_{i+1}| \le |a_{i+1} - a_{i+2}|\)를 만족하게 하려고 한다. \(1 \le i \le n-2\)

가능한 경우를 하나 출력하면 된다.

 

수들을 정렬 한 다음, \(n/2\)번째 수를 기준으로

\(n/2-1\)번째 수, \(n/2+1\)번째 수, \(n/2-2\)번째 수, \(n/2+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 n;
int a[100001];
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    int t; cin >> t;
    while (t--)
    {
        cin >> n;
        for (int i = 0; i < n; i++) cin >> a[i];
        sort(a, a + n);
 
        cout << a[n / 2];
        for (int i = 1; i <= (n - 1) / 2; i++)
        {
            cout << ' ' << a[n / 2 - i] << ' ' << a[n / 2 + i];
        }
        if (n % 2 == 0) cout << ' ' << a[0];
        cout << "\n";
    }
}

---

A - Powered Addition

Problem - A - Codeforces

길이 \(n\)의 수열 \(a\)가 주어진다.

\(x\)초가 될 때마다, 다음과 같은 연산을 1번씩 수행할 수 있다.

 

서로 다른 인덱스의 원소들을 선택한 다음, 그 원소들에 \(2^{x-1}\)을 더한다.

 

이 연산을 이용하여 \(a\)가 비내림차순이 되도록 하려고 한다.

이 때, \(a\)가 비내림차순이 되는 가장 빠른 시간을 구해야 한다.

 

\(a_i\)에 대하여, \(a_j > a_i\)인 \(1 \le j \lt i\) 가 존재한다면, \(a_j - a_i\)중 가장 큰 값을 \(D_i\)라고 하자.

\(max_{1\le i \le n}D_i\)의 최상위 비트가 \(b\)번째 비트라고하면, 적어도 \(b\)초가 지나야 차이를 메꿀 수 있음을 알 수 있다.

따라서 답은 \(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; }
 
ll n;
ll a[100001];
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    int t; cin >> t;
    while (t--)
    {
        cin >> n;
        for (int i = 0; i < n; i++) cin >> a[i];
 
        ll res = 0;
        ll tmp = a[0];
        for (int i = 1; i < n; i++)
        {
            if (a[i] >= tmp)
            {
                tmp = a[i];
                continue;
            }
 
            ll diff = tmp - a[i];
            res = max(res, diff);
        }
 
        ll ans = -1;
        for (ll i = 0; i < 40; i++)
        {
            if (res < (1ll << i))
            {
                ans = i;
                break;
            }
        }
 
        cout << ans << '\n';
    }
}

---

B - Edge Weight Assignment

Problem - B - Codeforces

정점의 개수가 \(n\)인 트리가 주어진다.

이 트리의 가중치를 임의로 정하려고 하는데, 리프노드에서 다른 리프노드까지 가는 경로의 가중치를 bitwise XOR한 값이 모두 0이 되어야 한다.

 

이 때, \(f\)를 이 트리에 있는 서로 다른 가중치의 개수라고 할 때,

\(f\)의 최솟값과 최댓값을 알아내야 한다.

 

먼저, 최솟값에 대해 생각해 보자.

관찰을 잘 해보면, 트리의 형태에 상관없이 3개의 수 (1,2,3) 만으로 위의 조건을 만족할 수 있게 가중치를 잘 정해줄 수 있음을 알 수 있다.

여기에 더해서, 모든 리프노드 사이의 거리가 짝수라면, 모든 가중치를 1개의 수로 정해도 위의 조건을 만족한다는 것 까지 알 수 있다.

 

모든 리프노드 사이의 거리가 짝수인지 판정은,

모든 정점에 대해서 리프노드 까지의 거리가 짝수인 경우만 존재하거나, 홀수인 경우만 존재하는지 확인하면 된다.

루트가 리프노드인 경우에 예외를 잘 처리해 주도록 하자.

 

다음은 최대값이다.

무조건 같은 수를 배정해야 하는 경우는 자명하다. 어떤 노드에 여러 개의 리프노드가 연결되어 있다면, 이 노드와 리프노드 사이의 가중치는 모두 같은 수여야 한다.

그 외에는 수의 크기에 제한이 없기 때문에, 모두 다른 수를 배정하면서 조건을 만족하도록 할 수 있음을 관찰로 알 수 있다.

 

#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;
vector <int> graph[100001];
int hasEven[100001], hasOdd[100001];
int isLeaf[100001];
 
bool hasOddLength = false;
void DFS(int v, int p) // even, odd
{
    int& even = hasEven[v];
    int& odd = hasOdd[v];
 
    if (graph[v].size() == 1)
    {
        isLeaf[v] = 1;
        if (v != 1) return;
    }
 
    for (auto nv : graph[v])
    {
        if (nv == p) continue;
        DFS(nv, v);
 
        if (isLeaf[nv])
        {
            odd |= 1;
        }
        else
        {
            even |= hasOdd[nv];
            odd |= hasEven[nv];
        }
    }
 
    if (even && odd) hasOddLength = true;
}
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    cin >> n;
    for (int i = 0; i < n - 1; i++)
    {
        int a, b; cin >> a >> b;
        graph[a].push_back(b);
        graph[b].push_back(a);
    }
 
    DFS(1, 0);
 
    int res = 0;
    for (int i = 1; i <= n; i++)
    {
        int cnt = 0;
        for (auto nv : graph[i])
        {
            if (isLeaf[nv]) cnt++;
        }
 
        res += max(0, cnt - 1);
    }
 
    if (isLeaf[1] && hasOdd[1]) hasOddLength = true;
 
    if (hasOddLength)
    {
        cout << "3 " << n - 1 - res;
    }
    else
    {
        cout << "1 " << n - 1 - res;
    }
}

---

C - Perfect Triples

Problem - C - Codeforces

다음의 규칙에 따라 무한 수열 \(s\)를 만드려고 한다.

 

1. 사전순으로 가장 앞서는 3개의 수 \((a,b,c)\)를 찾는데,

\(a \oplus b \oplus c = 0\) 이어야 하고, \(a,b,c\)가 모두 \(s\)에 존재 하지 않아야 한다.

2. 그 후 \(a,b,c\)를 차례대로 \(s\)에 추가한다.

 

수 \(n\)이 주어지고, 이 방식으로 \(s\)를 만들었을 때, \(n\)번째 항이 뭔지 알아내야 한다.

 

초기 몇 항들을 직접 만들어 보면, 규칙을 찾을 수 있다.

1,2,3 / 4,8,12 / 5,10,15 / 6,11,13 / 7,9,14

맨 앞 1,2,3은 제외하고 2진수로 바꿔보자.

 

01 00 / 10 00 / 11 00 (4, 8, 12)

01 01 / 10 10 / 11 11 (5, 10, 15)

01 10 / 10 11 / 11 01 (6, 11, 13)

01 11 / 10 01 / 11 10 (7, 9, 14)

 

앞의 2비트는 1, 2, 3로 고정이고,

뒤의 2비트는 (0, 0, 0), (1, 2, 3), (2, 3, 1), (3, 1, 2) 순서로 진행됨을 알 수 있다.

 

일반적으로, \(4^n-1\)까지의 수를 이런식으로 채웠다면,

다음 \(4^n\)부터 \(4^{n+1}-1\)까지의 수는 이전에 만들었던 수에 추가로 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 str[4][3] =
{
{0,0,0},
{1,2,3},
{2,3,1},
{3,1,2}
};
 
vector <ll> vec;
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    ll sum = 0;
    ll four = 4;
    vec.push_back(0);
    while (sum <= 1e16)
    {
        sum += four;
        vec.push_back(sum);
        four *= 4;
    }
 
    int t; cin >> t;
    while (t--)
    {
        ll n; cin >> n; n--;
        ll d = n / 3, r = n % 3;
 
        if (d == 0)
        {
            cout << r + 1 << '\n';
            continue;
        }
 
        int idx = lower_bound(vec.begin(), vec.end(), d) - vec.begin();
 
        d -= vec[idx - 1];
        d--;
 
        ll ans = 0;
        ll mul = 1;
 
        for (int i = 0; i < idx; i++)
        {
            ll rm = d % 4;
 
            ans += str[rm][r] * mul;
            mul *= 4;
 
            d /= 4;
        }
 
        ans += (r + 1) * mul;
 
        cout << ans << '\n';
    }
}

---

D - Nested Rubber Bands

Problem - D - Codeforces

추가 예정

---

E - JYPnation

Problem - E - Codeforces

추가 예정