Codeforces #728

A. Pretty Permutations

https://codeforces.com/contest/1541/problem/A

Problem - A - Codeforces

$n$마리의 고양이가 일렬로 늘어서 있다.

$i$번째 고양이는 $i$번째 자리에 위치해 있다.

어떤 고양이도 이전에 있던 자리에 있지 않도록 자리를 바꿔야 한다.

 

1) $n=2k$

$1 \le i \le \frac{n}{2}$, $2i-1$번째 고양이와 $2i$번째 고양이가 짝을 지어 자리를 바꾼다.

 

2) $n=2k-1$

처음 3마리의 고양이끼리 자리를 바꾼다. [1, 2, 3] $\rightarrow$ [3, 1, 2]

$2 \le i \le \frac{n}{2}$, $2i$번째 고양이와 $2i+1$번째 고양이가 짝을 지어 자리를 바꾼다.

 

#include <bits/stdc++.h>
using namespace std;
 
int main(void) {
    cin.tie(NULL);
    ios::sync_with_stdio(false);
 
    int t; cin >> t;
    while (t--) {
        int n; cin >> n;
        if (n%2) {
            cout << 3 << ' ' << 1 << ' ' << 2 << ' ';
            for (int i = 2; i <= n/2; i++) {
                cout << 2*i+1 << ' ' << 2*i << ' ';
            }
        }
        else {
            for (int i = 1; i <= n/2; i++) {
                cout << 2*i << ' ' << 2*i-1 << ' ';
            }
        }
        cout << '\n';
    }
    return 0;
}

 

 

 

B. Pleasant Pairs

https://codeforces.com/contest/1541/problem/B

Problem - B - Codeforces

$n$개의 서로 다른 정수가 담긴 배열 $a$가 주어진다.

$i \lt j$이면서 $a_i \cdot a_j = i + j$인 인덱스 쌍 $(i, j)$의 개수를 구해야 한다.

 

$a_i \cdot a_j = i+j$이므로 $a_i | (i+j)$이다.

$j = a_i \cdot k - i$인 $j$에 대해 $a_j = k$인지 조사해보면 된다. (단, $i \lt j \le n$임을 주의)

 

#include <bits/stdc++.h>
using namespace std;
 
int main(void) {
    cin.tie(NULL);
    ios::sync_with_stdio(false);
 
    int t; cin >> t;
    while (t--) {
        int n; cin >> n;
        vector<int> v(n+1);
        for (int i = 1; i <= n; i++) {
            cin >> v[i];
        }
        int ans = 0;
        for (int i = 1; i < n; i++) {
            for (int j = v[i]-i; j <= n; j += v[i]) {
                if (j <= i) continue;
                if (v[j] == (i+j)/v[i]) ans++;
            }
        }
        cout << ans << '\n';
    }
    return 0;
}

 

 

 

C. Great Graphs

https://codeforces.com/contest/1541/problem/C

Problem - C - Codeforces

$n$개의 정점으로 이루어진 방향 그래프이다.

음의 간선이 존재할 수 있지만, 음의 사이클은 존재하지 않는다.

 

0번 정점으로부터 모든 정점들까지의 최소 거리($0 \le d_i \le 10^9$)가 주어질 때,

그래프에 포함된 간선들의 가중치 합이 최소가 되도록 만들어야 한다.

 

이를 위해선 양의 간선의 가중치 합과 음의 간선의 가중치 합이 최소가 되도록 만들어야 한다.

0번 정점으로부터 거리가 가장 먼 정점을 $a$라고 하자.

양의 간선은 유일하게 $(0, a)$ 하나만 존재한다.

모든 정점 $u$에 대해서, 정점 $u$와 $d_v \lt d_u$인 정점 $v$ 사이에 간선 $(u, v)$를 추가한다.

이때 해당 간선의 가중치는 $-(d_u - d_v)$이다.

 

간선의 가중치 합은 부분합 $psum$을 통해 구현할 수 있다.

음의 간선의 가중치들을의 절댓값을 나열해보면 다음과 같다.

$$a_1 - a_0$$

$$a_2 - a_0$$

$$a_2 - a_1$$

$$a_3 - a_0$$

$$a_3 - a_1$$

$$a_3 - a_2$$

$$\cdots$$

규칙을 통해 이들의 합이 $\sum_{i=1}^{n-1}{\{ i \cdot a_i - psum[i-1]\}}$임을 알 수 있다.

 

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
int main(void) {
    cin.tie(NULL);
    ios::sync_with_stdio(false);
 
    int t; cin >> t;
    while (t--) {
        int n; cin >> n;
        vector<ll> v(n);
        for (int i = 0; i < n; i++) {
            cin >> v[i];
        }
        sort(v.begin(), v.end());
        
        vector<ll> psum(n);
        psum[0] = 0;
        for (int i = 1; i < n; i++) {
            psum[i] = psum[i-1] + v[i];
        }
 
        ll ans = v.back();
        for (int i = 1; i < n; i++) {
            ans -= i*v[i];
            ans += psum[i-1];
        }
        cout << ans << '\n';
    }
    return 0;
}

 

 

 

D. Tree Array

https://codeforces.com/contest/1540/problem/B

Problem - B - Codeforces

 

/* 풀이 추가 예정 */

 

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
int n;
const int MAX = 202;
const int MOD = 1e9 + 7;
 
vector<vector<int> > adj(MAX);
int depth[MAX];
int par[MAX][8];
int dp[MAX][MAX];
 
void makeTree(int cur) {
    for (int nxt: adj[cur]) {
        if (depth[nxt] == -1) {
            depth[nxt] = depth[cur] + 1;
            par[nxt][0] = cur;
            makeTree(nxt);
        }
    }
}
 
int lca(int u, int v) {
    if (depth[u] < depth[v]) swap(u, v);
    int diff = depth[u] - depth[v];
    for (int i = 0; i < 8; i++) {
        if (diff & (1 << i)) u = par[u][i];
    }
    if (u != v) {
        for (int i = 7; i >= 0; i--) {
            if (par[u][i] != -1 && par[u][i] != par[v][i]) {
                u = par[u][i];
                v = par[v][i];
            }
        }
        u = par[u][0];
    }
    return u;
}
 
int modPow(int a, int k) {
    if (k == 0) return 1;
    ll ret = modPow(a, k/2);
    ret = (ret * ret) % MOD;
    if (k%2) return (ret * a) % MOD;
    else return ret;
}
 
int f(int a, int b) {
    if (dp[a][b] != -1) return dp[a][b];
    if (a == 0) return 0;
    if (b == 0) return 1;
    ll ret = ((ll)f(a-1, b) + f(a, b-1)) % MOD;
    return dp[a][b] = (ret * modPow(2, MOD-2)) % MOD;
}
 
int main(void) {
    cin.tie(NULL);
    ios::sync_with_stdio(false);
 
    cin >> n;
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
 
    ll ans = 0;
    for (int i = 1; i <= n; i++) {
        memset(depth, -1, sizeof depth);
        for (int j = 0; j < MAX; j++) {
            for (int k = 0; k < 8; k++) {
                par[j][k] = -1;
            }
        }
        depth[i] = 0; par[i][0] = -1;
        makeTree(i);
        for (int k = 1; k < 8; k++) {
            for (int j = 1; j <= n; j++) {
                if (par[j][k-1] != -1)
                    par[j][k] = par[par[j][k-1]][k-1];
            }
        }
 
        for (int j = 0; j < MAX; j++) {
            for (int k = 0; k < MAX; k++) {
                dp[j][k] = -1;
            }
        }
 
        ll tmp = 0;
        for (int j = 1; j <= n; j++) {
            for (int k = j+1; k <= n; k++) {
                int l = lca(j, k);
                int da = depth[j] - depth[l];
                int db = depth[k] - depth[l];
                tmp = (tmp + f(da, db)) % MOD;
            }
        }
        tmp *= modPow(n, MOD-2);
        tmp %= MOD;
 
        ans += tmp;
        ans %= MOD;
    }
    cout << ans;
    return 0;
}