COFO::Round #665 ( div 2 )

• Link : COFO::round 665(div 2)
• solved :
  • B : ( 00:49 )
  • C : ( 01:17 )
  • rank : 6511
  • score : 1792
• A에서 30분을 사용했지만 문제를 풀지 못했습니다.
  • 해설을 들어보니, 수학적 계산보다는 기하학적으로 그림을 좀 더 단순화하였다면 좋았을 것 같습니다.

Problem A : Distance and Axis

• tag : math
• B가 존재할 수 있게하는 A의 최소 이동거리 값을 출력합니다.
• 따라서 B의 위치를 출력하려 했던 제 최초 생각이 틀렸었고, 그랬기에 많은 시간을 소모했음에도 풀이하지 못하였습니다.

Point

• n과 k가 주어집니다.
• n은 점 A의 위치입니다.
• OB - AB 의 절댓값이 k와 일치하게 만드려고 합니다.
• 이때 점 B는 점 A를 이동시켜서 만들고자 할때,
• 위의 조건을 만족시키면서 A의 이동을 최소한으로 하여 B를 만드려고 합니다.
• 이때의 이동거리를 출력합니다.

Design

• A번 치고는 난이도가 있었다고 생각합니다.
• 에디토리얼에 올라온 설명 위주로 풀이하였습니다.
• n과 k가 주어졌을때 다음 두 가지 경우 중 하나이므로, 케이스 분류를 합니다.
• if(n < k)
  • 이 경우, b의 위치는 k 혹은 0 입니다.
  • 어쨌든, a는 k-n만큼 이동시켜야 합니다.
• else
  • 이 경우, b의 위치는 0과 a 사이에 있습니다.
  • b의 위치를 m이라고 해봅시다.
  • abs((m-0) - (n-m)) = k 가 성립해야 합니다.
  • 이 등식은 다음과 같이 정리될 수 있습니다.
  • m = (n-k)/2
  • 즉, 이러한 m은 항상 존재합니다.
  • 하지만, 소수점이 아닌 정수인 m이어야 하므로 끝에 0.5가 안 생기도록 parity를 맞춰주는 작업이 필요합니다.
  • 따라서, n과 k의 패리티값이 같은 경우 0을 출력하고
  • 다른 경우 1을 출력합니다.

Big O(time)

• O(1)

Big O(memory)

Code

// https://beenpow.github.io/
#include<bits/stdc++.h>
#define endl '\n'
#define pb push_back
#define f first
#define s second
#define all(v) (v).begin(), (v).end()
#define rep(i,a,b) for(int i=a;i<b;i++)
#define r_rep(i,a,b) for(int i=a;i>b;i--)
#define vi vector<int>
#define vpi vector<pair<int, int> >
typedef long long ll;
const int MAXN = 1000000 + 5, inf = 1e9;
using namespace std;
void process(){
    int n, k;
    cin >> n >> k;
    if(n < k) cout << k - n << endl;
    else{
        if(n%2 == k%2) cout << "0" << endl;
        else cout << "1" << endl;
    }
}
int main(){
    int tc; cin >> tc;
    while (tc--)
        process();
    return 0;
}

Problem B : Termary Sequence

• tag : constructive algorithms, greedy, math
• time : 00:49

Point

• 2개의 배열 a와 b가 주어집니다.
  • 각 배열에 포함된 0, 1, 2 의 갯수가 주어집니다.
• 주어진 0, 1, 2의 갯수를 가진 배열을 통해 배열 c를 만드려고 합니다.
  • 배열 a의 원소 a_i와 배열 b의 원소 b_i의 연산은 다음과 같이 진행됩니다.
  • if(ai > bi) ci = ai * bi
  • if(ai == bi) ci = 0
  • if(ai < bi) ci = -ai * bi
• 이때 가장 큰 배열 c의 총합을 출력합니다.

Design

• 처음 문제를 손으로 시뮬레이션 해볼때는 ai * bi 즉, 더해지는 값이 가장 큰 것에만 집중하였습니다.
• 하지만, 더하는 것보다 중요한 것은, 빼는 것이었습니다.
• 몇 번 시뮬레이션 해보면 다음의 규칙을 알 수 있습니다.
  • ai * bi 가 되는 경우는 ai의 값이 2이고, bi의 값이 1인 경우밖에 없습니다.
  • -ai * bi 가 되는 경우는 ai의 값이 1이고, bi의 값이 2인 경우밖에 없습니다.
  • 즉, ai에 포함된 2와 bi에 포함된 2가 정답을 maximize하는데 큰 요인이라는 점입니다.
• 따라서 저는 bi의 2의 갯수를 minimize하는 방법으로 풀이하였습니다.
• 먼저 ai의 0의 갯수를 최대한 활용하여 그 곱이 -0이 되도록 만들어 줍니다.
• 이후, 아직 bi의 2의 갯수가 남아있다면,
  • ai의 1의 갯수와 곱하여 그 갯수만큼 마이너스 해주고, 답을 구할 수 있습니다.

Big O(time)

• O(1)

Big O(memory)

Code

// https://beenpow.github.io/
#include<bits/stdc++.h>
#define endl '\n'
#define pb push_back
#define f first
#define s second
#define all(v) (v).begin(), (v).end()
#define rep(i,a,b) for(int i=a;i<b;i++)
#define r_rep(i,a,b) for(int i=a;i>b;i--)
#define vi vector<int>
#define vpi vector<pair<int, int> >
typedef long long ll;
const int MAXN = 1000000 + 5, inf = 1e8;
using namespace std;


void process(){
    int a0, a1, a2; cin >> a0 >> a1 >> a2;
    int b0, b1, b2; cin >> b0 >> b1 >> b2;
    int gap0_2 = min(a0, b2);
    a0 -= gap0_2, b2 -= gap0_2;
    if(b2 == 0){
        cout << 2 * 1 * min(a2, b1) << endl;
        return;
    }
    int gap2_2 = min(a2, b2);
    a2 -= gap2_2, b2 -= gap2_2;
    if(b2 == 0){
        cout << 2 * 1 * min(a2, b1) << endl;
        return;
    }
    cout << -1 * 1 * 2 * min(a1, b2) << endl;
}
int main(){
    int tc; cin >> tc;
    while (tc--)
        process();
    return 0;
}

Problem C : Mere Array

• tag : constructive algorithms, math, number theory
• time : 01:17

Point

• n이 주어집니다.
• n개의 원소로 이루어진 배열 a가 주어집니다.
• 작업을 통해 배열 a를 오름차순 정렬할 수 있는지 여부를 출력합니다.
• 작업은 다음과 같습니다.
  • 인덱스 i, j를 선택합니다.
  • if(gcd(ai, aj) == min(a))
  • ai와 aj 원소의 GCD가 배열 a의 최소값과 같은 경우,
  • swap(ai, aj)할 수 있습니다.

Design

• 먼저 배열 a를 복사하여 b를 만들고 정렬해둡니다.
• 또한 배열 a의 원소 중 가장 작은 값을 mn이라 하겠습니다.
• 그리고 다음의 조건을 만족한다면 원소는 마음대로 swap 될 수 있습니다.
• ai와 bi가 다른 경우,
  • ai가 mn으로 나누어 떨어지는 경우
• 즉, 자신의 자리(정렬 후)가 아닌 위치에 있는 원소들이 있습니다.
• 해당 원소들이 자신의 자리로 가려면, 일단 자기 자신이 움직일 수 있는 상태이어야 합니다.
• 움직일 수 있는 원소는 몇개가 되던 서로 스왑하여 그 원소들 내에서 자리를 마음대로 바꿀 수 있습니다.

Big O(time)

• O(NlogN)

Big O(memory)

Code

// https://beenpow.github.io/
#include<bits/stdc++.h>
#define endl '\n'
#define pb push_back
#define f first
#define s second
#define all(v) (v).begin(), (v).end()
#define rep(i,a,b) for(int i=a;i<b;i++)
#define r_rep(i,a,b) for(int i=a;i>b;i--)
#define vi vector<int>
#define vpi vector<pair<int, int> >
typedef long long ll;
const int MAXN = 1000000 + 5, inf = 1e9;
using namespace std;

int n;
vi a, b;
vi ans;
void process(){
    cin >> n;
    a.resize(n);
    
    int mn = inf;
    rep(i, 0, n){
        cin >> a[i];
        mn = min(mn, a[i]);
    }
    
    b = a;
    sort(all(b));
    
    rep(i, 0, n) if(a[i] != b[i]){
        if(a[i] % mn != 0 || a[i] < mn){
            cout << "NO" << endl;
            return;
        }
    }
    
    cout << "YES" << endl;
}
int main(){
    int tc; cin >> tc;
    while (tc--)
        process();
    return 0;
}

Problem D : Maximum Distributed Tree

• tag : dfs and similar, dp, greedy, number theory, sortings, trees
• 문제 이해에 하기의 유튜브 동영상을 참고하였습니다.
• Link::Colin Galen

Point

• n이 주어집니다.
• n-1개의 간선이 주어집니다.
• n-1개의 간선을 통해 트리를 구성합니다.
• 간선의 값이 주어집니다.
• 이때, 다음 공식의 최대값을 출력합니다.
• sum_from_i=1_to_i=n-1 ( sum_from_j=i+1_to_n ( f(i, j) ) )
• f(i, j)는 정점 i와 j사이의 path에 존재하는 모든 간선의 길이의 합 입니다.
  • 트리는 두 정점 사이에 존재하는 경로가 1개뿐입니다.

Design

• 문제에서 요구하는 바는 결국, 각 간선에 주어진 값들을 적절히 배치하고,
• 길이의 총합을 구하라는 것입니다.
• 하지만, 라운드 진행당시, 트리 내에 존재하는 두 정점 사이의 길이를 구하는 방법을 찾아내지 못하였습니다.
• 방법은 다음과 같습니다.
• 루트를 기준으로 트리를 구성합니다.
  • 이때 각 정점의 서브트리에 존재하는 정점의 갯수와 해당 정점에 연결된 간선의 곱을 구해줍니다.
• 그 이유는 다음과 같습니다.
  • 문제에 주어진 식을 그대로 해석하자면 노드와 노드 사이의 길이를 구해야 하고,
  • 이들을 모두 그려보면,
  • 상위 부모 노드일수록 자식의 갯수만큼 길에 사용되는 것을 알 수 있기때문입니다.
• 이를 위해, dfs를 통해 자식의 갯수를 sz[]배열에 담습니다.
  • 이후 벡터 v에 sz[u] * (n - sz[u])을 push해 줍니다.
  • 그 이유는, 해당 정점 u에서 자식방향으로 가는 간선은 해당 갯수만큼 사용되기 떄문입니다.
  • 즉, 해당 정점 기준으로 부모 방향으로 n-sz[u]개의 정점이 존재하고, 자식방향으로는 sz[u]개의 정점이 존재하기 때문입니다.
• 위의 dfs를 통해 각 간선이 사용되는 횟수인 벡터 v를 구성하였습니다.
• 큰 값 * 큰 값을 해야 총 합을 maximize 시킬 수 있으므로 v를 내림차순 정렬합니다.
• 이제 해당 간선에 값을 부여할 차례입니다.
• m의 갯수에 따라 2가지 방법으로 나뉩니다.
• if(n-1 <= m)
  • 이 경우가 조금 특이합니다.
  • 먼저 n-2개의 간선에 m개 중 작은 n-2개를 부여합니다.
  • 그리고 하나의 간선(v값 중 가장 큰 값(가장 많이 사용되는 간선) )에 남은 m-(n-2)개의 수를 모두 곱해서 부여합니다.
  • 왜냐하면, 모든 간선의 곱이 k이어야 하기 떄문입니다.
  • 또한, 하나의 prime이 하나의 간선에만 할당되어야 한다는 정의는 없기 때문입니다.
• if(n-1 > m)
  • 이 경우, v[0]부터 m개에 순서대로 값을 부여해주고, 나머지 n-1 - (m)개에는 1을 부여해줍니다.
• 중요한 법칙 하나를 알아둬야 할 것 같습니다.
  • 배열 a와 b가 내림차순으로 정렬되어있습니다.
  • 배열 a와 배열 b의 원소 하나씩을 짝지어서 그 곱의 총합을 구할때, 해당 값을 가장 크게 하려면
  • 큰 값과 큰 값을 곱해야 maximize시킬 수 있습니다.
  • 증명은 에디토리얼에 제시되어있습니다.

Big O(time)

• max(O(NlogN), O(MlogM))

Big O(memory)

Code

// https://beenpow.github.io/
#include<bits/stdc++.h>
#define endl '\n'
#define pb push_back
#define f first
#define s second
#define all(v) (v).begin(), (v).end()
#define rep(i,a,b) for(int i=a;i<b;i++)
#define r_rep(i,a,b) for(int i=a;i>b;i--)
#define vi vector<int>
#define vll vector<ll>
#define vpi vector<pair<int, int> >
typedef long long ll;
const int MAXN = 100000 + 5, inf = 1e9;
#define MOD 1000000007
using namespace std;

int n, m;
vi adj[MAXN];

int sz[MAXN];
vll v;
void dfs(int here, int prev){
    sz[here] = 1;
    for(auto there : adj[here]){
        if(there == prev) continue;
        dfs(there, here);
        sz[here] += sz[there];
    }
    if(here != 1) v.pb( 1LL * sz[here] * (n - sz[here]));
}

void process(){
    cin >> n;
    
    // init
    rep(i, 0, n+1) adj[i].clear(), sz[i] = 0;
    //w.clear();
    v.clear();
    
    rep(i, 0, n-1){
        int u, v; cin >> u >> v;
        adj[u].pb(v);
        adj[v].pb(u);
    }
    cin >> m;
    vll w (m, 0);
    rep(i, 0, m) cin >> w[i];
    
    
    dfs(1, 0);
    
    sort(v.rbegin(), v.rend());
    sort(w.rbegin(), w.rend());
    
    ll ans = 0;
    int cnt = max(1, m - (n-1) + 1); // n-1 >= m ,  n-1 < m
    int j = 0;
    ll val = v[0] % MOD;
    while(cnt > 0){
        val *= w[j++];
        val %= MOD;
        cnt--;
    }
    
    ans += val; //  the largest part
    ans %= MOD;
    
    rep(i, 1, v.size()){
        if(j < w.size()) ans += v[i] * w[j++];
        else ans += v[i];
        ans %= MOD;
    }
    cout << ans << endl;
}
int main(){
    int tc; cin >> tc;
    while (tc--)
        process();
    return 0;
}