Codeforces Round #636 (Div. 3)

A - Candies

Problem - A - Codeforces

양의 정수 \(n\)이 주어진다.

\(x+2x+4x+\cdots+2^{k-1}x=n\), (\(k \gt 1\))을 만족하는 \(x\)를 출력해야 한다.

 

단순히 가능한 모든 \(k\)에 대해 계수의 합을 만든다음 \(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; }
 
vector <ll> dv;
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    ll tmp = 4;
    while (tmp < 1e9)
    {
        dv.push_back(tmp - 1);
        tmp *= 2;
    }
 
    int t; cin >> t;
    while (t--)
    {
        ll n; cin >> n;
        for (auto it : dv)
        {
            if (n % it == 0)
            {
                cout << n / it << '\n';
                break;
            }
        }
    }
}

---

B - Balanced Array

Problem - B - Codeforces

짝수 \(n\)이 주어지면, 길이가 \(n\)인 수열 \(a\)를 다음의 조건에 맞게 만들어야 한다.

 

1. 첫 \(\frac n2\)개의 원소는 짝수이다.

2. 다음 \(\frac n2\)개의 원소는 홀수이다.

3. 모든 원소는 서로 다른 양수이다.

4. 수열의 첫 \(\frac n2\)개의 원소의 합과 다음 \(\frac n2\)개의 원소의 합은 서로 같다.

 

먼저 \(n\)이 4로 나눠 떨어지지 않는다면 만드는 것이 불가능하다.

짝수와 홀수를 각각 홀수 개씩 더해서 같은 수를 만들 수 없기 때문이다.

 

그렇지 않다면, 첫 \(\frac n2\)개의 원소는 짝수를 작은 순으로 나열하고,
다음 \(\frac n4\)개의 원소는 첫 \(\frac n4\)개의 원소에서 1을 뺀 값을,
그 다음 \(\frac n4\)개의 원소는 두 번째 \(\frac n4\)개의 원소에서 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 main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    int t; cin >> t;
    while (t--)
    {
        int n; cin >> n;
        if (n / 2 % 2)
        {
            cout << "NO\n";
            continue;
        }
 
        cout << "YES\n";
        for (int i = 0; i < n / 2; i++) cout << i * 2 + 2 << ' ';
        for (int i = 0; i < n / 4; i++) cout << i * 2 + 1 << ' ';
        for (int i = n / 4; i < n / 2; i++) cout << i * 2 + 3 << ' ';
        cout << '\n';
    }
}

---

C - Alternating Subsequence

Problem - C - Codeforces

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

 

어떤 수열의 모든 원소가 이웃한 원소와 부호가 다르다면 이 수열을 alternating 수열이라고 하자.

\(a\)의 가장 길이가 긴 alternating 부분 수열중, 모든 원소의 합이 가장 큰 부분 수열을 찾아 그 합을 출력해야 한다.

 

수열이 주어지면, 앞에서부터 양수로만 이루어진 덩어리와 음수로만 이루어진 덩어리로 나눌 수 있다.

 

ex) -2 8 3 8 -4 -15 5 -2 -3 1

→ -2 / 8 3 8 / -4 -15 / 5 / -2 -3 / 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[200001];
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    int t;  cin >> t;
    while (t--)
    {
        cin >> n;
        for (int i = 0; i < n; i++) cin >> a[i];
 
        int ans_sz = 0;
 
        bool isPositive = (a[0] > 0);
 
        ll res = 0;
        ll tmp = a[0];
        for (int i = 0; i < n; i++)
        {
            if (isPositive != a[i] > 0)
            {
                isPositive = !isPositive;
                res += tmp;
 
                tmp = a[i];
            }
 
            tmp = max(tmp, a[i]);
        }
        res += tmp;
 
        cout << res << "\n";
    }
}

---

D - Constant Palindrome Sum

Problem - D - Codeforces

길이가 \(n\)인 수열 \(a\)가 주어진다. 모든 원소의 값은 \(k\)를 초과하지 않는다.

 

이 수열의 원소 하나를 다른 수로 바꾸는 연산을 할 수 있는데, 연산 후에 수열이 다음 조건을 만족하도록 해야 한다.

 

1. 모든 연산 후에, 모든 원소의 값이 \(k\)를 초과하면 안된다.

2. 모든 \(1 \le i \le \frac n2\)에 대하여 \(a_i+a_{n-i+1}=x\)를 만족해야 하는데, \(x\)는 모든 \(\frac n2\)쌍에 대해 모두 같아야 한다.

 

이 때 가능한 연산 수의 최소값을 구해야 한다.

 

먼저 연산 수의 상한에 대해 생각해보자.

모든 쌍 \((l,r)\)에 대해 \(l\)은 그대로 두고, \(r\)을 \(k+1-l\)로 바꾸는 연산을 하면 위의 조건을 무조건 만족하게 된다.

따라서 답의 상한이 \(n/2\)임을 알 수 있다.

 

다음은 어떤 쌍 \((l,r)\)에 대해 이 쌍을 그대로 두고, 다른 모든 쌍의 합이 \(l+r\)이 되도록 맞춰준다고 생각해보자.

두 값의 합이 \(l+r\)인 쌍의 개수를 \(s\)라고 하고 역시 나머지 쌍에 대해 둘 중 한 값만 바꾼다고 생각하면 답이 \(n/2-s\)라고 생각할 수 있는데, 잘 생각해보면 두 값을 모두 바꿔야만 하는 경우가 있다.

 

1. 두 값중 큰 값이 \(s-k\)보다 작을 때

2. 두 값중 작은 값이 \(s\)보다 크거나 같을 때

 

위 조건을 만족하는 쌍의 수는 각 쌍의 최소/최대 값의 개수를 저장한다음, 부분합을 구해놓음으로써 \(O(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, k;
ll a[200001];
 
int min_cnt[200001];
int max_cnt[200001];
 
map <ll, int> mp;
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    int t; cin >> t;
    while (t--)
    {
        mp.clear();
 
        cin >> n >> k;
 
        for (int i = 0; i <= k; i++) min_cnt[i] = max_cnt[i] = 0;
        for (int i = 0; i < n; i++) cin >> a[i];
 
        for (int i = 0; i < n / 2; i++)
        {
            min_cnt[min(a[i], a[n - 1 - i])]++;
            max_cnt[max(a[i], a[n - 1 - i])]++;
 
            int num = a[i] + a[n - 1 - i];
            mp[num]++;
        }
 
        for (int i = 1; i <= k; i++)
            max_cnt[i] += max_cnt[i - 1];
 
        for (int i = k - 1; i >= 0; i--)
            min_cnt[i] += min_cnt[i + 1];
        
        int ans = n / 2;
        for (auto it : mp)
        {
            int res = n / 2 - it.second;
            
            int min_num = it.first - k;
 
            if (min_num > 1)
                res += max_cnt[min_num - 1];
 
            int max_num = it.first - 1;
            
            if (max_num < k)
                res += min_cnt[max_num + 1];
 
            ans = min(ans, res);
        }
 
        cout << ans << '\n';
    }
}

---

 

E - Weights Distributing

Problem - E - Codeforces

\(n\)개의 정점과 \(m\)개의 간선으로 이루어진 그래프가 주어지고, 이 그래프의 간선에 붙일 수 있는 \(m\)개의 가중치가 주어진다.

 

이 그래프의 3개의 정점 \(a,b,c\)가 주어지고, 이 정점을 순서대로 방문하려고 한다. (방문 하는 중에 간선이 중복되어도 상관없다.)

이 때, 가중치를 적절히 설정해서, 위 정점들을 순서대로 방문할 때의 가중치의 합이 최소가 되도록 하려고 한다.

그 때의 가중치를 구해야 한다.

 

그래프가 어떤 형태이든간에, \(a\)에서 \(d\), \(b\)에서 \(d\), \(c\)에서 \(d\)로 최단거리로 이동했을 때 경로가 서로 겹치지 않는 정점 \(d\)가 존재한다. (\(d\)가 \(a,b,c\)중 하나 일 수도 있다.)

 

그러면 가능한 모든 정점 \(d\)에 대해서, 우리가 지나는 실제 경로는

\(a \rightarrow d \rightarrow b \rightarrow d \rightarrow d \rightarrow c\)가 될 것이다.

두 번씩 지나는 \(b\)와 \(d\)사이의 가중치를 가장 작게 하고, 그 외 지나는 경로들을 남은 가중치 중 가장 작은 것들로 채운다면

\(d\)가 정해졌을 때의 경로 가중치의 최솟값을 알 수 있다.

 

따라서 정점 \(a,b,c\)각각에 대해 BFS를 돌려 다른 정점까지의 거리를 알아낸 다음, 모든 정점에 대해 이 정점을 \(d\)로 설정 했을 때의 경로 가중치의 최솟값을 각각 구한 다음, 그 중 최솟값을 구하면 된다.

 

이 때 \(a\)에서 \(d\), \(b\)에서 \(d\), \(c\)에서 \(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; }
 
int n, m;
int a[3];
vector <int> graph[200001];
ll p[200001];
 
int dist[3][200001];
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    int t; cin >> t;
    while (t--)
    {
        cin >> n >> m >> a[0] >> a[1] >> a[2];
 
        for (int i = 1; i <= n; i++)
        {
            graph[i].clear();
            dist[0][i] = dist[1][i] = dist[2][i] = -1;
        }
 
        for (int i = 1; i <= m; i++) cin >> p[i];
 
        sort(p + 1, p + m + 1);
        for (int i = 1; i <= m; i++) p[i] += p[i - 1];
 
        for (int i = 0; i < m; i++)
        {
            int a, b; cin >> a >> b;
            graph[a].push_back(b);
            graph[b].push_back(a);
        }
 
        for (int k = 0; k < 3; k++)
        {
            dist[k][a[k]] = 0;
            queue <int> q;
            q.push(a[k]);
 
            while (!q.empty())
            {
                int v = q.front(); q.pop();
                for (auto nv : graph[v])
                {
                    if (dist[k][nv] != -1) continue;
 
                    dist[k][nv] = dist[k][v] + 1;
                    q.push(nv);
                }
            }
        }
 
        ll ans = numeric_limits<ll>::max();
        for (int i = 1; i <= n; i++)
        {
            int da = dist[0][i];
            int db = dist[1][i];
            int dc = dist[2][i];
 
            if (da + db + dc > m) continue;
            ll res = p[da + db + dc] + p[db];
            ans = min(ans, res);
        }
 
        cout << ans << '\n';
    }
}

---

F - Restore the Permutation by Sorted Segments

Problem - F - Codeforces

\(n\)개의 수로 이루어진 순열 \(p\)가 있다.

 

이 순열에 대한 힌트로, \(2\)부터 \(n\)사이의 모든 \(r\)에 대하여,

\(p_l, p_{l+1}, \cdots , p_r\)이 정렬된 상태로 주어진다. (\(l<r\))

 

이 힌트들을 이용해 원래 순열이 뭔지 알아내야 한다.

 

관찰로써 알 수 있는 사실 중에 하나는, 순열의 맨 마지막 원소는 힌트 내에서 무조건 단 한번만 등장한다는 것이다.

 

그렇다면 다음의 알고리즘으로 순열을 복원할 수 있겠다는 생각을 할 수 있다.

1. 힌트 전체에서 단 한번만 존재하는 수를 현재 순열의 맨 마지막 원소로 설정한다.

2. 그 수가 등장하는 힌트를 제외한 다음, 1번으로 돌아간다.

 

그런데 한 가지 예외가 있다. 맨 첫번째 원소도 단 1번만 등장할 수도 있다.

이를 해결하기 위해서, 맨 첫 번째 원소를 \(k\)로 정해놓은 다음, 이 한 가지 원소로만 이루어진 힌트를 추가하자. (\([k]\))

그리고 위의 알고리즘으로 순열을 복원했을 때, 만드는 도중에 한 번만 등장하는 수가 없거나, 복원된 수열이 힌트와 모순이 된다면 첫 번째 원소가 \(k\)가 아님을 알 수 있게 된다.

 

남은 것은 구현이다. \(n\)이 작으므로 \(O(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 n;
int isUsed[201];
vector <vector<int> > k;
 
vector <int> idx[201];
int cnt[201];
int tcnt[201];
 
bool isValid(vector <int>& res)
{
    if (res.size() < n) return false;
 
    int idx[201];
    for (int i = 0; i < n; i++)
        idx[res[i]] = i;
 
    for (auto& vec : k)
    {
        set <int> st;
        for (auto num : vec) st.insert(idx[num]);
 
        int fr = *st.begin();
        int bk = *prev(st.end());
 
        if (bk - fr + 1 != st.size()) return false;
    }
 
    return true;
}
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    int t; cin >> t;
    while (t--)
    {
        k.clear();
        memset(cnt, 0, sizeof cnt);
 
        cin >> n;
        for (int i = 1; i <= n; i++) idx[i].clear();
 
        for (int i = 0; i < n - 1; i++)
        {
            vector <int> tmp;
            int s; cin >> s;
 
            for (int j = 0; j < s; j++)
            {
                int x; cin >> x;
                tmp.push_back(x);
                idx[x].push_back(i);
                cnt[x]++;
            }
 
            k.push_back(tmp);
        }
 
        vector <int> ans;
 
        for (int fr = 1; fr <= n; fr++)
        {
            memset(isUsed, 0, sizeof isUsed);
            memcpy(tcnt, cnt, sizeof cnt);
            tcnt[fr]++;
            vector <int> tmpVec = { fr };
            k.push_back(tmpVec);
            idx[fr].push_back(n - 1);
 
            vector <int> res;
            for (int i = 0; i < n; i++)
            {
                int cnum = 0;
                for (int j = 1; j <= n; j++)
                {
                    if (tcnt[j] == 1)
                    {
                        cnum = j;
                        break;
                    }
                }
 
                if (cnum == 0) break;
                if (cnum == 0) break;
 
                int ckidx = 0;
                res.push_back(cnum);
                for (auto kidx : idx[cnum])
                {
                    if (isUsed[kidx]) continue;
                    ckidx = kidx;
                }
 
                isUsed[ckidx] = 1;
                for (auto it : k[ckidx])
                    tcnt[it]--;
            }
 
            if (isValid(res)) ans = res;
 
            k.pop_back();
            idx[fr].pop_back();
        }
 
        reverse(ans.begin(), ans.end());
        for (auto it : ans) cout << it << ' ';
        cout << '\n';
    }
}