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

A - Strange Partition

Problem - A - Codeforces

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

이 배열의 인접한 두 원소를 합치는 연산을 원하는 만큼 할 수 있을 때,

\(\sum^k_{i=1} \lceil \frac{b_i}{x} \rceil\)의 최소값과 최대값을 구해야 한다.

 

배열의 값을 전부 합쳤을 때가 최소값이고, 한 번도 합치지 않았을 때가 최대값이다.

 

#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, x;
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    int t; cin >> t;
    while (t--)
    {
        cin >> n >> x;
 
        ll mn = 0, mx = 0;
        ll sum = 0;
        for (int i = 0; i < n; i++)
        {
            ll a; cin >> a;
            sum += a;
            mx += (a - 1) / x + 1;
        }
 
        mn = (sum - 1) / x + 1;
 
        cout << mn << ' ' << mx << '\n';
    }
}

---

B - Strange List

Problem - B - Codeforces

\(n\)길이의 배열 \(a\)와 \(x\)가 주어진다.

이 배열을 첫 원소부터 탐색해 나간다.

\(a_i\)가 \(x\)로 나누어 떨어진다면, 배열의 맨 끝에 \(x\)개의 \(\frac{a_i}{x}\)를 추가한다.

그렇지 않다면, 그 자리에서 탐색을 종료한다.

 

탐색이 종료된 후에 배열의 모든 원소의 합을 알아내야 한다.

 

직접 시뮬레이팅해도 \(O(n\log n)\)의 시간에 답을 알아낼 수 있다.

뒤에 직접 \(x\)개의 수를 붙이는게 아니라 단순히 \(x\)개가 있다고 표시만 해두면 된다.

 

 

#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, x;
ll a[100001];
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    int t; cin >> t;
    while (t--)
    {
        cin >> n >> x;
 
        ll ans = 0;
        for (int i = 0; i < n; i++)
        {
            cin >> a[i];
            ans += a[i];
        }
 
        ll mul = 1;
        while (true)
        {
            bool flag = true;
            for (int i = 0; i < n; i++)
            {
                if (a[i] % x)
                {
                    flag = false;
                    break;
                }
 
                ans += a[i] * mul;
                a[i] /= x;
            }
 
            mul *= x;
 
            if (!flag) break;
        }
 
        cout << ans << '\n';
    }
}

---

A - Strange Birthday Party

Problem - A - Codeforces

\(n\)명의 사람이 있고, 각각 \(k_i\)라는 수를 배정 받았다. 이 사람들에게 선물을 주려고 한다.

상점에는 서로 다른 \(m\)개의 선물이 있고, \(j\)번째 선물의 가격은 \(c_j\)이다.

선물은 비내림차순으로 진열되어 있다.

 

각 사람들에게 \(j \le k_i\)번째 선물을 사주거나, \(c_{k_i}\)원을 직접 줄 수 있다.

각 선물은 최대 1번씩만 살 수 있다고 할 때, 돈이 최소 얼마나 필요한지 알아내야 한다.

 

 

\(k_i\)가 큰 사람일 수록 싼 선물을 주는 것이 무조건 이득이다.

남은 선물중 가장 싼 것보다 \(c_{k_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; }
 
int n, m;
int k[300001];
ll c[300001];
 
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 >> k[i];
        for (int i = 1; i <= m; i++) cin >> c[i];
 
        vector <ll> vec;
        for (int i = 1; i <= n; i++)
        {
            vec.push_back(c[k[i]]);
        }
 
        sort(vec.rbegin(), vec.rend());
 
        int ptr = 1;
        ll ans = 0;
 
        for (ll x : vec)
        {
            if (ptr <= m && c[ptr] < x) ans += c[ptr++];
            else ans += x;
        }
 
        cout << ans << '\n';
    }
}

---

B - Strange Definition

Problem - B - Codeforces

어떤 두 정수 \(x, y\)에 대해, \(\frac{lcm(x,y)}{gcd(x,y)}\)가 제곱수라면 두 수를 가깝다고 하자.

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

 

1초가 지날 때마다, 각각의 원소 \(a_i\)는 \(a_i\)와 가까운 서로 다른 모든 원소들의 곱으로 바뀐다.

\(d_i\)를 \(a_i\)와 가까운 원소의 수라고 가정하자.

이 배열의 beauty는 \(d_i\)의 최대값이다.

 

\(w\)가 주어지면, \(w\)초 후에 이 배열의 beauty를 출력해야 한다.

 

 

조건을 잘 분석해보면, 어떤 원소 \(a_i\)의 약수 \(x\)가 제곱수라면, \(a_i\)를 \(x\)로 나누어도 결과에 아무 영향을 끼치지 않는다는 사실을 알 수 있다.

 

이런식으로 배열을 모두 변경하고 나면, 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;
ll a[300001];
 
vector <int> p;
 
map <int, int> mp;
map <int, int> ans;
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    p.push_back(2);
    for (int i = 3; i <= 1000; i++)
    {
        bool flag = true;
        for (int j = 0; j < p.size() && p[j] * p[j] <= i; j++)
        {
            if (i % p[j] == 0)
            {
                flag = false;
                break;
            }
        }
 
        if (flag) p.push_back(i);
    }
 
    int t; cin >> t;
    while (t--)
    {
        mp.clear();
        ans.clear();
 
        cin >> n;
        for (int i = 0; i < n; i++)
        {
            cin >> a[i];
            ll x = a[i];
            int vec = 1;
 
            for (int j : p)
            {
                if (x % j == 0)
                {
                    int cnt = 0;
                    while (x % j == 0)
                    {
                        x /= j;
                        cnt++;
                    }
 
                    if (cnt % 2) vec *= j;
                }
            }
 
            if (x != 1) vec *= x;
 
            mp[vec]++;
        }
 
        ll tm = 0;
        int last = 0;
 
        while (true)
        {
            int res = 0;
            bool flag = false;
 
            map <int, int> tmp;
            for (auto& it : mp)
            {
                int cnt = it.second;
                res = max(res, cnt);
 
                if (it.first != 1 && cnt % 2 == 0)
                {
                    tmp[1] += cnt;
                    flag = true;
                }
                else tmp.insert(it);
            }
 
            ans[tm++] = res;
            last = res;
 
            if (!flag) break;
 
            mp = tmp;
        }
 
        int q; cin >> q;
        while (q--)
        {
            ll w; cin >> w;
 
            //cout << "ANS:";
            if (w >= tm) cout << last << '\n';
            else cout << ans[w] << '\n';
        }
    }
}

---

C - Strange Shuffle

Problem - C - Codeforces

\(n\)명의 사람들이 둥글게 앉아있다.

각각의 사람들은 초기에 \(k\)장의 카드를 가지고 있다.

한 턴이 지날 때마다 \(\lfloor x/2 \rfloor\)장의 카드를 왼쪽 사람에게, \(\lceil x/2 \rceil\)장의 카드를 오른쪽 사람에게 넘기게 된다.

 

하지만 이 중 한 사람이 트롤이라서, 한 턴이 지나면 모든 카드를 오른쪽 사람에게 넘긴다.

 

한번의 쿼리로, 현재 \(x\)번 사람이 몇 장의 카드를 가지고 있는지 알 수 있다.

한번의 쿼리를 쓴 후에는 한 턴이 지나가게 된다.

 

최대 1000번의 쿼리로 누가 트롤인지 알아내야 한다.

 

 

관찰을 통해 다음과 같은 사실을 알 수 있다.

1. 트롤은 항상 정확히 \(k\)장의 카드를 갖는다.

2. 트롤의 오른쪽에 있는 사람부터 시작해 왼쪽에 있는 사람까지 카드의 수는 비오름차순이다.

 

따라서, 트롤보다 카드의 수가 적은 사람과 많은 사람을 한 명씩만 찾으면, 이분탐색으로 트롤의 위치를 알 수 있게 된다.

이 두 사람을 찾는 방법에는 여러가지가 있는데, 나는 쿼리가 매우 많이 남는다는 점을 이용해 랜덤으로 찾았다.

 

 

#include <bits/stdc++.h>
#include <random>
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;
ll query(ll q)
{
    cout << "? " << q << endl;
    ll res; cin >> res;
    return res;
}
 
int main()
{
    cin >> n >> k;
    random_device rd;
    mt19937 gen(rd());
    uniform_int_distribution<int> dis(1, n);
 
    int l = 0, r = 0;
    while (l == 0 || r == 0)
    {
        int num = dis(gen);
        int res = query(num);
 
        if (res < k) l = num;
        else if (res > k) r = num;
    }
 
    if (l > r) r += n;
 
    l++;
    while (l + 1 < r)
    {
        int m = (l + r) / 2;
 
        int qm = m;
        if (qm > n) qm -= n;
        int res = query(qm);
 
        if (res > k) r = m;
        else l = m;
    }
 
    if (l > n) l -= n;
    cout << "! " << l << endl;
}

---

D - Strange Housing

Problem - D - Codeforces

\(n\)개의 정점과 \(m\)개의 간선으로 이루어진 그래프가 주어진다.

이 그래프의 정점에 선생님들을 투입해, 다음과 같은 조건을 만족하게 하려고 한다.

 

1. 어떤 간선의 양 끝 정점 중 한 쪽에 선생님이 있어야 해당 간선을 이용할 수 있다.

2. 어떤 간선의 양 끝 정점 둘 다 선생님이 있을 수는 없다.

3. 이용할 수 있는 간선을 이용해 모든 정점이 연결되어 있어야 한다.

 

조건을 만족하는것이 가능한지 알아내고, 가능하다면, 추가로 선생님의 위치를 출력하면 된다.

 

 

초기에 주어지는 그래프가 연결되어 있지 않다면 불가능하다.

연결되어 있다면 무조건 가능하다. 2번 조건만 만족하도록 하면서 최대한 선생님을 추가하면 된다.

 

#include <bits/stdc++.h>
#include <random>
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, m;
vector <int> graph[300001];
 
int cache[300001];
 
void DFS(int v)
{
    cache[v] = 1;
    for (int nv : graph[v])
    {
        if (cache[nv]) continue;
        DFS(nv);
    }
}
 
int ans[300001];
void DFS2(int v)
{
    cache[v] = 1;
    bool flag = true;
    for (int nv : graph[v])
    {
        if (ans[nv] == 1) flag = false;
    }
 
    if (flag) ans[v] = 1;
    else ans[v] = 0;
 
    for (int nv : graph[v])
    {
        if (cache[nv]) continue;
        DFS2(nv);
    }
}
 
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++)
        {
            graph[i].clear();
            cache[i] = 0;
            ans[i] = -1;
        }
 
        for (int i = 0; i < m; i++)
        {
            int u, v; cin >> u >> v;
            graph[u].push_back(v);
            graph[v].push_back(u);
        }
 
        DFS(1);
 
        bool hasAns = true;
        for (int i = 1; i <= n; i++)
        {
            if (!cache[i]) hasAns = false;
            cache[i] = 0;
        }
 
        if (!hasAns)
        {
            cout << "NO\n";
            continue;
        }
 
        cout << "YES\n";
 
        DFS2(1);
 
        vector <int> res;
        for (int i = 1; i <= n; i++)
        {
            if (ans[i]) res.push_back(i);
        }
 
        cout << res.size() << '\n';
        for (int v : res) cout << v << ' ';
        cout << '\n';
    }
}

---

E - Strange Permutation

Problem - E - Codeforces

추가 예정

---

F - Strange Covering

Problem - F - Codeforces

추가 예정