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

A - Pretty Permutations

Problem - A - Codeforces

\(n\)마리의 고양이와 \(n\)개의 집이 있다. \(i\)번째 고양이는 \(i\)번째 집에 살고 있다.

모든 고양이가 원래 살던 곳이 아닌 집에 가서 살려고 할 때, 고양이의 이동 거리의 합의 최소값을 구해야 한다.

 

\(n\)이 짝수면, 인접한 2마리씩 짝지어 집을 교환하면 된다.

\(n\)이 홀수면, 첫 3마리를 서로 바꿔 준다음, 나머지를 짝수일 때 방법으로 처리하면 된다.

 

#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;
 
        int k = 1;
        if (n % 2) cout << "3 1 2 ", k = 4;
        while (k + 1 <= n) cout << k + 1 << ' ' << k << ' ', k += 2;
        cout << '\n';
    }
}

---

B - Pleasant Pairs

Problem - B - Codeforces

 

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

\(a_i \cdot a_j = i+j\)를 만족하는 \(i < j\)인 인덱스 쌍 \((i,j)\)의 개수를 구해야 한다.

 

\(a_i\)가 모두 서로 다르기 때문에, 어떤 수가 어디에 있는지 저장해 놓을 수 있다.

어떤 수 \(x\)에 대해, 곱이 \(x\)가 두 수는 \(O(\sqrt n)\)에 알 수 있으므로,

1부터 400000까지 모든 수에 대해 각각 구해주면 된다.

 

#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; }
 
map <int, int> mp;
 
int n;
int a[200001];
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    int t; cin >> t;
    while (t--)
    {
        mp.clear();
 
        cin >> n;
        for (int i = 1; i <= n; i++)
        {
            cin >> a[i];
            mp[a[i]] = i;
        }
 
        ll ans = 0;
        for (ll i = 2; i <= 2 * n; i++)
        {
            for (ll x = 1; x * x < i; x++)
            {
                if (i % x) continue;
                ll y = i / x;
                if (mp.find(x) == mp.end()) continue;
                if (mp.find(y) == mp.end()) continue;
                if (mp[x] + mp[y] == i) ans++;
            }
        }
 
        cout << ans << '\n';
    }
}

---

A - Great Graphs

Problem - A - Codeforces

 

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

이 방향그래프의 간선에는 정점간의 이동 시간을 나타내는 가중치가 존재한다.

음의 가중치가 존재할 수는 있지만, 가중치의 합이 음수인 사이클은 존재하지 않는다.

 

1번 정점에서 다른 정점까지 이동하는데 필요한 최소 시간을 나타내는 배열 \(d\)가 주어진다.

이를 이용해 원래의 방향 그래프를 복원해야 하는데, 모든 간선의 가중치의 합이 최소가 되도록 해야 한다.

 

이때 모든 간선의 가중치의 합을 구해야 한다.

 

 

\(d\)를 정렬하자.

걸리는 시간이 짧은 순으로 차례대로 방문함으로써, 양수인 간선의 가중치의 합을 최소화 할 수 있다.

이 상태에서 음수 간선을 가능한 만큼 추가해주면 될 것이다.

모든 걸리는 시간이 긴 정점에서 짧은 정점 사이에 가능한 작은 가중치의 음수간선을 추가해주면 된다.

 

#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 d[100001];
ll psum[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 = 1; i <= n; i++) cin >> d[i];
        sort(d + 1, d + n + 1);
 
        for (int i = 1; i <= n; i++) psum[i] = psum[i - 1] + d[i];
 
        ll ans = d[n];
 
        for (int i = 2; i <= n; i++)
        {
            ans -= d[i] * i - psum[i];
        }
        cout << ans << '\n';
    }
}

---

B - Tree Array

Problem - B - Codeforces

 

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

이 트리에 다음과 같은 규칙으로 색칠을 하려고 한다.

 

1. 랜덤으로 시작 정점을 하나 고른다.

2. 지금까지 골라진 정점과 거리가 1 떨어진 모든 정점 중 하나를 랜덤으로 고른다.

3. 트리가 모두 색칠 될 때까지 2번을 반복한다.

 

이 트리의 정점이 색칠된 순서를 배열로 만들었을 때, 배열의 inversion의 개수의 기대값을 알아내야 한다.

 

 

먼저, 루트가 정해져 있는 트리에서 정점 \(u, v\) (\(u < v\))에 대해, inversion이 일어날 확률을 계산해 보자.

(\(u\)보다 \(v\)가 먼저 선택 될 확률)

 

두 정점의 LCA까지는 색칠 되어도 아무 영향을 끼치지 않는다.

또, LCA에서 두 정점까지의 거리만이 확률에 영향을 끼친다는 사실을 관찰로써 알 수 있다.

 

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

\(dp_{i, j}\) : LCA에서 거리가 \(i\)떨어진 정점 \(u\)와 \(j\)떨어진 정점 \(v\)사이에 inversion이 일어날 확률 (\(u < v\))

\(i = 0\)이면 0, \(j = 0\)이면 1이 될 것이고, 그렇지 않은 경우에는 다음과 같은 점화식을 만들 수 있다.

\(dp_{i, j} = \frac{dp_{i-1,j}}{2} + \frac{dp_{i,j-1}}{2}\)

 

 

특정한 정점 \(x\)을 루트로 잡고, 모든 \((u, v)\) 정점 쌍에 대해 위에서 계산한 inversion이 일어날 확률을 모두 더하면 \(x\)가 루트일 때 inversion이 일어날 확률을 구할 수 있다.

 

이를 모든 정점에 대해 구한 값의 평균이 문제의 답이 된다.

 

시간복잡도는 앞의 브루트포스에 \(O(n^3)\), LCA에 \(O(\log n)\)이므로 총 \(O(n^3\log 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; }
 
const ll MOD = 1e9 + 7;
 
ll n;
vector <int> graph[201];
int dist[201];
int par[10][201];
 
ll mpow(ll a, ll n)
{
    if (n == 0) return 1;
    ll res = mpow(a, n / 2);
    res = res * res % MOD;
    if (n % 2) res = res * a % MOD;
    return res;
}
 
int lca(int a, int b)
{
    int la = dist[a], lb = dist[b];
    if (la > lb)
    {
        swap(a, b);
        swap(la, lb);
    }
 
    int d = lb - la;
    for (int k = 0; k < 10; k++)
    {
        if (d & (1 << k)) b = par[k][b];
    }
 
    if (a == b) return a;
 
    for (int k = 9; k >= 0; k--)
    {
        if (par[k][a] == par[k][b]) continue;
        a = par[k][a];
        b = par[k][b];
    }
 
    return par[0][a];
}
 
ll dp[201][201];
ll solve(int a, int b)
{
    ll& ret = dp[a][b];
    if (ret != -1) return ret;
    if (a == 0) return ret = 0;
    if (b == 0) return ret = 1;
 
    ll res1 = solve(a - 1, b);
    ll res2 = solve(a, b - 1);
 
    return ret = (res1 + res2) % MOD * mpow(2, MOD - 2) % MOD;
}
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    cin >> n;
 
    memset(dp, -1, sizeof dp);
    for (int i = 0; i <= n; i++) for (int j = 0; j <= n; j++)
        solve(i, j);
 
    for (int i = 0; i < n - 1; i++)
    {
        int u, v; cin >> u >> v;
        graph[u].push_back(v);
        graph[v].push_back(u);
    }
 
    ll ans = 0;
    for (int v = 1; v <= n; v++)
    {
        ll res = 0;
 
        memset(dist, -1, sizeof dist);
        dist[v] = 0; par[0][v] = v;
        queue <int> q; q.push(v);
        while (!q.empty())
        {
            int cv = q.front(); q.pop();
            for (int nv : graph[cv])
            {
                if (dist[nv] != -1) continue;
                dist[nv] = dist[cv] + 1;
                par[0][nv] = cv;
                q.push(nv);
            }
        }
 
        for (int k = 1; k < 10; k++)
        {
            for (int cv = 1; cv <= n; cv++)
                par[k][cv] = par[k - 1][par[k - 1][cv]];
        }
 
        for (int va = 1; va <= n; va++)
        {
            for (int vb = va + 1; vb <= n; vb++)
            {
                int ca = va, cb = vb;
                int l = lca(ca, cb);
 
                ll ta = dist[ca] - dist[l];
                ll tb = dist[cb] - dist[l];
 
                ll tmp = solve(ta, tb);
 
                res += tmp;
                res %= MOD;
            }
        }
 
        res *= mpow(n, MOD - 2);
        res %= MOD;
 
        ans += res;
        ans %= MOD;
    }
 
    cout << ans;
}

---

C - Converging Array (Hard Version)

Problem - C2 - Codeforces

추가 예정

---

D - Inverse Inversions

Problem - D - Codeforces

추가 예정

---

E - Tasty Dishes

Problem - E - Codeforces

추가 예정