Codeforces Round #714 (Div. 2) 풀이

 

 

codeforces.com/contest/1513

그동안 문제 풀고 틀린 건 그냥 넘어가는 경우가 많다 보니

비슷한게 또 나오면 또 틀렸던 경우가 많아서(모르는건 모르는거더라..) 가급적 풀이를 보고 이해할 수 있는 데까지 이해해 보기로 했다.

A. Array and Peaks

길이 n인 배열에서 peak의 개수가 k인 임의의 배열을 만든다.

index가 0부터 시작하는 기준 홀수번째 index의 위치들이 peak가 될 수 있는 위치이며, k가 이 수보다 많으면 불가능하다.

가능한 경우 k개의 peak의 위치의 가장 큰 수 부터 순서대로 집어놓고, 나머지 peak가 아닌 부분에는 수가 감소하는 순서로 그대로 넣으면 된다.

 

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
const int MAX = 2e9;

int main()
{
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int t;
    cin >> t;
    while(t--){
        int n , k;
        cin >> n >> k;
        vector<int>v(n);
        if(k > (n-1)/2){
            cout << -1<<"\n";
            continue;
        }
        int val = n;
        for(int i = 1; i < n && k>0; i+=2, k--){
            v[i]= val--;
        }
        for(int i =0; i <n; i++){
            if(!v[i]){
                v[i] = val--;
            }
            cout << v[i]<<" ";
        }
        cout << "\n";
    }
}

 

C. Add One

tag : dp

 

수의 최종 길이를 세주는 문제이기 때문에, 받은 수를 각각의 자릿수로 생각해 준 뒤

 

dp[x][d] : 수 x에 연산을 d번 했을 때 나오는 수의 길이로 놓고 d가 9인 경우 다음 0과 1로 나눠지는 것만

유의하여 dp를 돌리면 된다.

 

행렬곱을 이용한 형태로도 풀린다고 한다.

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
const ll MOD = 1e9 + 7;
ll dp[11][200005];
ll rec(ll x,ll d){
    ll &ret = dp[x][d];
    if(ret != -1)return ret;
    ret =0;
    if(d < 10 - x){
        ret = 1;
        return ret;
    }
    d -= (10-x);
    ret = (ret + rec(1,d))%MOD;
    ret = (ret + rec(0,d))%MOD;
    return ret;
}
int main()
{
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int t;
    cin >> t;
    memset(dp,-1,sizeof(dp));
    while(t--){
        string s;
        cin >> s;
        ll d;
        cin >> d;
        ll ans= 0;
        for(char c : s){
            ans = (ans + rec(c-'0', d))%MOD;
        }
        cout << ans<<"\n";
    }
}

 

B. AND Sequences

에디토리얼 원리는 유사하고 풀이가 더 짧고 간결하긴 하지만 이해를 못하겠어서 내가 푼 방식대로 올린다.

 

문제 조건에서 처음과 끝에 주목해 보자면

 

a1 = a2 & a3 & .... & an

an = an-1 & a2 & .... &1

 

즉, 처음과 끝에 들어가는 원소들은 나머지 원소를 전부 and 연산한 값과 같아야 한다.

이 때 처음과 끝에 들어갈 수 있는 수의 개수를 k라 하자.

모든 수를 비트처리한 것을 더해두고,

각각의 수를 한번씩 보면서 이 수와 나머지 수를 and 한 수가 같은 경우에만 (bit처리 해뒀으므로 한번에 바로 계산가능하다)

k를 더해주면 된다.

 

배열의 양 끝인 a1,an이 자리의 위치할 수를 k개의 수 중에서 2개 뽑고 - > $ kP2 $

나머지 자리는 그냥 배치하면 되므로 -> $ (n-2)! $

위 두 수를 곱한 것이 답이다.

 

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
const int MAX = 2e9;
const ll MOD = 1e9 + 7;
ll NP2(ll x) {
    return x * (x - 1) % MOD;
}
int main()
{
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int t;
    cin >> t;
    while (t--) {
        vector<int>cnt(33);
        int n;
        cin >> n;
        vector<int>v(n);
        ll k = 0;
        ll ans = 1;
        for (int& i : v)cin >> i;
        for (int i : v) {

            int bc = 0;
            int vi = i;
            while (vi) {
                if (vi & 1)cnt[bc]++;
                bc++;
                vi /= 2;
            }

        }
        for (int i : v) {
            int bc = 0;
            int vi = i;
            while (vi) {
                if (vi & 1)cnt[bc]--;
                bc++;
                vi /= 2;
            }
            int mynum = 0;
            for (int j = 31; j >= 0; j--) {
                if (cnt[j] == n - 1)mynum += (1 << j);
            }
            if (mynum == i)k++;
            bc = 0;
            vi = i;
            while (vi) {
                if (vi & 1)cnt[bc]++;
                bc++;
                vi /= 2;
            }
        }
        ans = (ans * NP2(k)) % MOD;;
        n -= 2;
        while (n--) {
            ans = (ans * (n+1)) % MOD;
        }
        if (k < 2)ans = 0;
        cout << ans << "\n";
    }
}

D. GCD and MST

tag : union-find, MST(kruskal algorithm)

 

문제 조건에서 gcd(ai,ai+1,... aj) = min(ai,ai+1, ... aj)를 만족하는 경우에 i- j 사이에 간선이 존재하고,

i가 시작노드이자, 최소값을 가진다 할 때, j가 후보가 되고, 식을 만족하려면, aj는 ai의 배수 형태여야만 한다. 

 

처음에는 이 조건에 따라, 연결할 수 있는 모든 노드를 연결한 뒤, 크루스칼 알고리즘을 통해 구하려고 했지만, 가능한 간선의 개수가 최대 n^2(n<= 200000) (배열 a의 원소가 모두 동일한경우)이 될 수 있다는 문제점이 있었다.

즉, 간선을 전부 받아 놓고 하는 것이 아닌, 가중치가 작은 간선부터 보면서 MST를 만들어나가면 된다.

 

•  가중치가 작은 간선 , 즉 ai가 적은 노드부터 시작점인 i로 잡고
• 위 조건을 만족하면서, 만약 두 노드 i, j가 아직 연결되지 않은 경우( disjoint-set을 이용해서 확인) i, j를 있는 간선을 추가해서 넣어준다.
• 이걸 모든 노드가 연결됬거나 (간선의개수가 n-1개가 되거나), 간선의 가중치가 p이상이 될 경우가 될 때 까지 반복 한 후, mst가 아직 되지 않은 경우 부족한 간선의 수만큼 p를 곱해서 더해준다.

 

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
const int MAX = 2e9;
int uf[200001];
int find(int x){
    if(uf[x]< 0)return x;
    return uf[x] = find(uf[x]);
}
bool merge(int a,int b){
    a = find(a), b = find(b);
    if(a==b)return 0;
    uf[a] = b;
    return 1;
}
int main()
{
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int t;
    cin >> t;
    while(t--){
        int n , p;
        cin >> n >> p;
        vector<int>a(n);
        vector<pi> v;
        for(int i =0; i < n; i++)uf[i] = -1;

        for(int i=0; i < n; i++){
            cin >> a[i];
            v.push_back({a[i],i});
        }
        sort(v.begin(), v.end());
        int ecnt =0;
        ll ans= 0;
        for(auto [val, ind] : v){
            if(val > p)break;
            int i = ind;
            while(i > 0){
                if(a[i - 1] % val == 0 && merge(i-1, ind)){
                    i--; ecnt++;
                    ans += val;
                }
                else break;
            }
            i = ind;
            while(i < n - 1){
                if(a[i + 1] % val == 0 && merge(i+1, ind)){
                    i++; ecnt++;
                    ans += val;
                }
                else break;
            }
        }
        ecnt = n - 1 - ecnt;
        ans += 1LL * ecnt * p;
        cout << ans << "\n";
    }
}

E. Cost Equilibrium

tag : combinatorics, constructive algorithms

 

풀면서는 문제를 제대로 이해하지도 못했고, 에디토리얼을 계속 보고나서야 겨우 이해했지만,

문제를 푸는 과정에서 어떻게 접근해야 할지 알 수 있는 문제였다.

문제 정의 부터 꼼꼼하게 보는 것이 중요한데,

 

• beautiful array : 배열 a의 모든 원소가 동일한 배열
• 조건 을 만족하는 a의 원소로 이루어진 순열의 개수를 구해야한다. (balanced array)
• 조건 :  배열이 주어질 때, 연산 을 임의로(any) 사용해서 beautiful array 로 만들 수 있다. 이 때, 연산을 어떤 순서로 사용 하던간에 최종 비용이 같아야 한다. (연산을 사용해서 beautiful array로 만들때의 최소 비용과 최대 비용이 같아야 한다.)
• 연산(operations) :  두 인덱스 i, j를 각각 source 와 sink 로 삼고, source에서 x를 빼고, sink에서 x를 더해준다. (x는 임의로 지정 가능), 이 때, 한번 sink인 노드는 source가 될 수 없으며, 그 역도 성립한다. 이 연산의 비용은            $ abs(i - j) * x $ 이다

일단,배열 a의 원소가 전부 동일하게 만들 때, 만들 값을 val 이라 하자.

연산의 조건 상에서 source인 경우 source만 , sink인 경우 sink만 될 수 있기 떄문에, 최종적으로 모든 원소에서 val로 만들기 위해 더해줘야 하는 값(ai가 val보다 작은 경우)과 val로 만들기 위해 빼줘야 하는 값 (ai가 val보다 큰 경우) 은 동일해야 한다.

 

-> 결론 : 배열 a의 모든원소의 합 S가 n으로 나누어지는 경우 (s % n == 0)에만 가능하고, 이 때 만들 값인 val은 s / n이다.

 

연산을 통하여 동일하게 만들 수 있는지 여부를 알았으니

이제 연산을 어떻게 하던 비용이 동일하게 되는 순열의 개수를 구하면 된다.

다음의 2가지 조건 중 하나를 만족하면, 연산을 어떻게 하던 비용이 동일하게 될 수 있다.

배열 a의 모든 원소들을 다음과 같이 구분해주자.

• source : ai > x 인 모든 원소
• sink :  ai < x 인 모든 원소
• 기타  : ai == x인 모든 원소

1) source나 sink가 단 1개인 경우

 

source나 sink가 단 1개로 정해져 있으므로, 나머지 노드들을 어떻게 배치하던 연산의 비용은 동일하다.

즉 모든 a의 원소를 순열배치 하는 모든 경우의 수

$ n! / f1! * f2! *... fk! $  를 구해주면 된다.  (  $ f_i $ : 배열에서 원소 i가 등장하는 빈도)

 

2)모든 source 노드 다음에 sink노드가 나오거나모든 sink 노드 다음에 source 노드가 나오는 경우

 

왜 다음 조건을 만족하는 경우 최소 비용과 최대 비용이 동일할까?

연산에 필요한 비용은 각 {source, sink}의 index { i , j } 의 절대값 차이와 바뀌어야 되는 값, 2가지로 이루어진다.

이 때, source 와 sink에서 바뀌어야하는 값 x는 정해져 있고, 유일하므로

source와 sink index의 절대값 차이만을 고려하면 된다.

즉 위 조건을 만족해야지만 source와 sink의 절대값 차이의 합이 (i, j)를 어떤 방식으로 고르든 일정해진다.

 

source를 배치하는 경우와 sink를 배치하는 경우는 1번과 동일하게 같은 원소를 고려하여 순열 배치하는 방법의 수로 구하면 되고, 2를 곱해준다 (source 다음 sink , sink 다음 source)

이제 기타 원소들을 배치하면 되는데, 이는 (source + sink의 개수 + 1) 개의 자리에 기타 원소의 개수 만큼 중복을 허락해서 배치하는 경우의 수, 즉 중복조합 $ (source+sink+1)H(n-source-sink) $ 이고,  이는 $ nC(n-source-sink) $ 와 동일하다.

 

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
const int N = 1e5 + 5;
const ll MOD = (ll)1e9 + 7;
ll fac[N], inv[N]; // fac[i] 의 역원
int n;
ll mypow(ll a, ll b) {
    ll res = 1;
    while (b) {
        if (b & 1) {
            res = (res * a) % MOD;
        }
        a = (a * a) % MOD;
        b >>= 1;
    }
    return res%MOD;
}

ll ncr(ll n, ll r) {
    if(r==0)return 1;
    ll ret = fac[n];
    ret = (ret * mypow(fac[r], MOD - 2)) % MOD;
    ret = (ret * mypow(fac[n - r], MOD - 2)) % MOD;
    return ret;
}

ll solv(){
    int n;
    cin >> n;
    vector<ll>v(n);
    ll sum = 0;
    ll ans = 1;
    for(ll &i : v){
        cin >> i;
        sum += i;
    }
    // 모든 값의 합을 n으로 나눈 나머지가 0이 아니라면?? -> 모든 원소를 같게 만들수 없다
    if(sum % n != 0)return 0;
    ll val = sum / n ;

    int src =0, snk = 0; // source, sink에 해당하는 원소의 개수
    map<int,int> srcm, snkm; // source, sink에 해당하는 각 원소가 등장하는 빈도

    for(ll &i : v){
        if(i > val){
            src++;
            srcm[i]++;
        }
        else if(i < val){
            snk++;
            snkm[i]++;
        }
    }
    // 모든 원소가 동일한 경우
    if(src ==0 && snk == 0)return 1;

    // src또는 sink가 1개존재하는 경우
    if(src == 1 || snk == 1){
        ans = fac[n];
        for(auto &[f,s] : srcm)ans =(ans * inv[s])%MOD;
        for(auto &[f,s] : snkm)ans =(ans * inv[s])%MOD;
        int rest = n - src - snk;
        ans = (ans * inv[rest]) % MOD;
        return ans;
    }

    // 나머지
    ans = ((2 * fac[src])%MOD * fac[snk]) % MOD;

    for (auto &[f, s] : srcm)
        ans = (ans * inv[s]) % MOD;

    for (auto &[f, s] : snkm)
        ans = (ans * inv[s]) % MOD;
    
    int rest = n - src - snk;

    // (n-rest+1)Hrest --> nCrest
    ans = (ans * ncr(n,rest))%MOD;
    return ans;

}

int main()
{
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);

    fac[0] = 1, inv[0] = 1;
    for(int i = 1; i < N; i++){
        fac[i] = (fac[i-1]*i)%MOD;
        inv[i] = mypow(fac[i], MOD- 2);
    }

    cout << solv();

}

F. swapping problem

조건을 잘 나눠서 처리한 뒤 새그먼트 트리를 이용하여 nlgn에 구할 수 있다고 한다. 나중에 도전해보는걸로..